Many to Many Taxonomies or rewrite rules?

With reservations, sure, you can do what you want with this code:

add_action('init', 'wpse_61376_rewrites');
function wpse_61376_rewrites() {
    add_rewrite_rule('^([^/]*)/([^/]*)/?$','index.php?category=$matches[1]&location=$matches[2]','top');
}

Then go to Settings → Permalinks in wp-admin and click “Save Changes” to flush your rewrites and activate this rule.

Reservations

The problem about not having a prefix is that any permalink with two “sections” (site.com/section-1/section-2/) will be caught by this permalink and you will end up with undesirable behavior at times. For instance, an entry with two pages, site.com/about/2 or a comments feed for a page, site.com/page/feed/. Long story short, this is ill-advised.

Suggested Solution

If it were me, I would add a static base for safety. You said this was for a directory, so that seems a good base:

add_action('init', 'wpse_61376_rewrites');
function wpse_61376_rewrites() {
    add_rewrite_rule('^directory/([^/]*)/([^/]*)/?$','index.php?category=$matches[1]&location=$matches[2]','top');
}

Your URLs would then be, site.com/directory/shops/miami/, which is as intuitive as it is safe.