use dijkstras algorithm to find the shortest path from vertex a to vertex l. give your answer as a sequence…
use dijkstras algorithm to find the shortest path from vertex a to vertex l. give your answer as a sequence of vertexes, like abc
Answer
Explanation:
Step1: Initialize distances
Set distance of A to 0, others to infinity. Let dist[A]=0, dist[B]=inf, dist[C]=inf, etc.
Step2: Explore neighbors of A
Neighbors are B and D. dist[B]=5, dist[D]=22. Mark A as visited.
Step3: Select unvisited vertex with min distance
Select B. Explore its neighbors C and E. dist[C]=5 + 26=31, dist[E]=5+1 = 6. Mark B as visited.
Step4: Select unvisited vertex with min distance
Select E. Explore its neighbors F and H. dist[F]=6 + 13=19, dist[H]=6+14 = 20. Mark E as visited.
Step5: Select unvisited vertex with min distance
Select F. Explore its neighbor I. dist[I]=19+20 = 39. Mark F as visited.
Step6: Select unvisited vertex with min distance
Select H. Explore its neighbor K. dist[K]=20+24 = 44. Mark H as visited.
Step7: Select unvisited vertex with min distance
Select I. Explore its neighbor L. dist[L]=39+23 = 62. Mark I as visited.
Step8: Back - track to find path
Back - track from L to A using the previous - vertex information. The shortest path is ABEFIL.
Answer:
ABEFIL