Question

Use Dijkstra's Algorithm to find the shortest path from a to z

Answer 1

@Zarkon

Answer 2

@king can u check this out?

Answer 3

I haven't worked with dijkstra's algorithm at all, but it seems like you would do the following:

1. Mark everything unvisited, set a as the current vertex.
2. Mark the tentative distance to e as 4, and tentative distance to b as 1.
3. Mark a as visited.
4. Move to b, and set this as current.
5. Mark tentative distance to c as 1+1=2, and the tentative distance to f as 1+1=2.
6. Mark b as visited.
7. Move to c, set as the current.
8. Mark tentative distance to d as 2+1=3, and tentative distance to g as 2+8=10.
9. Mark c as visited.
10. Move to f, and set as current.
11. Mark tentative distance to e as 2+1=3 and overwrite previous value of 4, mark tentative distance to g as 2+1=3 and overwrite previous value of 10.
12. Mark f as visited.
13. Move to d, set as current.
14. Mark tentative distance to z as 3+20=23.
15. Mark d as visited.
16. Move to g, set as current.
17. Mark tentative distance to z as 3+1=4, and overwrite previous value of 23.
18. Mark g as visited.
19. Move to e, set as current.
20. No more neighbors, so mark minimum distance as 3.
21. Mark e as visited.
22. Move to z, set as current.
23. z has no more neighbors, so mark minimum distance as 4.
24. Mark z as visited.
25. z is destination, so the algorithm ends, outputs distance of 4.

Answer 4

Every time I move to a new node, it's the node with the least tentative distance. If there are two with the same tentative distance, I just chose the one with the "least" letter.

Answer 5

ok thankkkss KING GEORGE. U R THE BEST :D

Answer 6

You're welcome.