J'ai un graphique pondéré bi-direction avec environ 5000 nœuds et j'ai une liste de nœuds "importants" (100 ou plus). Étant donné un nœud de départ et un nœud de fin, comment puis-je trouver la distance la plus courte entre ces deux nœuds qui passent au moins 1 des nœuds "importants". Notez qu'il n'y a pas de bords négatifs. J'ai implémenté l'algorithme de dijkstra pour trouver la distance la plus courte étant donné deux nœuds. Et le seul moyen que je connaisse pour résoudre ce problème serait de parcourir la liste des nœuds importants, en trouvant la distance depuis le début -> importantNoeud # 1 -> fin pour tous les nœuds importants puis en prenant le minimum. Existe-t-il un moyen plus rapide de résoudre ce problème?comment trouver la distance la plus courte entre deux nœuds qui passent au moins l'un des nœuds obligatoires?
0
A
Répondre
1
Votre approche est absolument correcte, ce dont vous avez besoin est d'appliquer Dijkstra moins de fois. Ce problème peut facilement être résolu en appliquant Dijkstra seulement deux fois.
Appliquer Dijkstra avec début comme source. Stockez les distances dans le tableau à partir de S.
Appliquer Dijkstra une fois de plus. Cette fois prendre fin comme source. Enregistrez les distances dans le tableau à E. Étant donné que votre graphique est la distance la plus courte non orientée entre et la fin noeud à tous les autres nœuds est la même que la distance la plus courte de tous les autres nœuds au nœud fin. (C'est le truc).
Trouvez la distance minimale requise.
For node in importantNodes : ans = min (fromS [node] + toE[node] , ans) return ans