Création d'un noeud du plus court chemin de la file d'attente à l'aide de dijkstra

Question

J'ai le chemin le plus court calculé à l'aide d'un algorithme dijkstra correctement implémenté. Il va de A à F via B, C, D et E. Donc le chemin le plus court est [A, B, C, D, E, F]. Maintenant, je veux passer de G à F. Quand je sors C de la file, je réalise qu'il fait partie du chemin le plus court vers F. Est-ce que cela veut dire que je sais aussi que le chemin le plus court de G à F est [ G, H, C, D, E, F]?

Answer 1

Non, mais il ne dire que le plus court chemin de C à F est [C, D, E, F].

S'il y avait un chemin plus court, P nous contruct un nouveau chemin de A à F [A, B, [P]] qui est intrinsèquement plus court que notre chemin original. Ceci est une contradiction car nous avons supposé que [A, B, C, D, E, F] était le chemin le plus court de A à F.

Cela peut être généralisé pour prouver que le sous-chemin d'un chemin le plus court est aussi un chemin le plus court. Dans votre cas, cela signifie que si le chemin le plus court de G à F contient C, alors ce chemin le plus court contient [C, D, E, F] comme sous-chemin. Puisque vous ne savez pas si C est dans votre chemin le plus court, ce théorème ne vous aidera à réduire le nombre de calculs que si vous stockez le poids du chemin le plus court de C à F.

Answer 2

Je ne pense pas, puisque vous devez prendre en compte la distance de H à C. si la distance [H, C] est énorme, disons supérieure à la distance [H, SI]?