Bi Directional Dijkstra

Dijkstra bidirectionnels

Problème

Étant donné un graphique avec des poids de bord non négatifs, un sommet source S et un sommet cible t . Trouvez le chemin le plus court entre S et T

Mais pourquoi n'utilisons-nous pas simplement l'algorithme de Dijkstra pour résoudre le problème?

0 (e + vlogv) est la pire complexité du temps de l'algorithme de Dijkstra qui est assez rapide. Mais, pour un graphique avec 20 millions de sommets et 50 millions de bords, cela fonctionnera en moyenne pendant plusieurs secondes. Nous avons donc besoin de quelque chose de considérablement plus rapide.

Avant d'entrer dans les détails de la recherche bidirectionnelle, explorons le concept de "six degrés de séparation"

• En 1929, un auteur hongrois, Frigyes Karinthy, a proposé pour la première fois le concept de "six degrés de séparation" dans ses chaînes de nouvelles.
• Six degrés de séparation sont l'idée que tous les êtres vivants et tout le reste dans le monde sont à six pas ou moins les uns des autres.

Maintenant, regardons le réseau social le plus populaire, Facebook. Supposons qu'une personne moyenne sur Facebook compte environ 100 amis. Ensuite, si nous considérons les amis des amis de cette personne, ce sera 100 * 100, c'est 10 000 amis d'amis. Si nous considérons les «amis des amis des amis» , ce sera 100 fois plus ou 1 million. Et si nous continuons cela six fois, nous aurons 1 milliard de personnes.

Mais, la population mondiale est de 7,6 milliards.

Maintenant, comment pouvons-nous trouver le chemin le plus court entre deux personnes aléatoires A et B via leurs connexions sur le réseau social?

Passons en compte la recherche bidirectionnelle. Nous considérerons donc les amis des amis de A et les amis des amis de B. Si le concept de six degrés de séparation est vrai, il y aura une personne commune entre les amis des amis de A et les amis des amis de B., alors nous pouvons facilement trouver le chemin le plus court qui relie A et B.

Notez que nous aurons environ 1 million d'amis d'amis d'amis pour A et B. Donc, au total, nous ne considérerons que 2 millions de personnes dans ce cas.

L'algorithme normal de Dijkstra devrait chercher environ 2 milliards de personnes sur le réseau social pour trouver le chemin le plus court entre A et B.

Qu'est-ce que la recherche bidirectionnelle

En cela, nous effectuons deux recherches simultanées: une en avant de l'état initial, et un en arrière du but, s'arrêtant lorsque les deux se rencontrent au milieu.

Pseudocode pour dijkstra bidirectionnelle sur le graphique g

• Construire GR (graphique inversé)
• Démarrer Dijkstra à partir de S (source) en g et de t (cible) dans GR
• Alterner entre les étapes de dijkstra en g et en gr
• Arrêtez-vous quand un sommet "V" est traité à la fois en g et gr.
• Calculez le chemin le plus court entre S et T.

Le calcul du chemin le plus court entre S et T: Soit dist [u] l'estimation de la distance dans les dijkstra avant de S dans G. Soit dist [u] l'estimation de la distance dans les dijkstra arrière de T dans Gr. Une fois que certains nœuds "V" sont traités à la fois en g et Gr, un chemin le plus court de S à T passe par un nœud "u" qui est traité soit en g, en gr ou les deux et d (s, t) = dist [u] + dist [u]