CODEWITHSUNDEEP
algorithmdijkstra
Hlkwtz
Hlkwtz

Reputation: 3

How can Dikjstra find the shortest path in this graph?

I'm having trouble understanding how Dijkstra finds the shortest path (from the way I understand it works) in the following graph if we have to find the shortest path from 0 to 3: https://graphonline.ru/tmp/saved/SH/SHBqKyENwJqcCJGM.png

If the algorithm chooses the smallest weight from 0 and marks 0 as visited, wouldn't it choose node 1 then node 3? how would it choose node 2?

Upvotes: 0

Views: 155

Answers (3)

eesiraed
eesiraed

Reputation: 4654

Dijkstra's algorithm involves a priority queue where all nodes directly reachable from a visited node are kept, along with their distances to the starting node.

The algorithm will visit node 0, and add node 1 and 2 to the priority queue. Then it will visit node 1 since it is the closest node in the priority queue, and add node 3 to the priority queue with a distance of 6. Node 2 is still in the queue, and since it is closer to node 0 than node 3, it will be visited next. When node 2 is visited, a shorter path of length 4 to node 3 will be found, so the distance to node 3 will be updated to 4. Node 3 will then be visited.

Upvotes: 2

Mark Pichler
Mark Pichler

Reputation: 26

From my understanding, the algorithm recalculates the tentative distances of the neighboring, unvisited, vertices before choosing the next vertex to visit. When you are at 1, you first recalculate the tentative distance of its neighboring unvisted vertices, in this case 3. Then choose the unvisited node with the shortest tentative distance, in this case 2, and visit that node.

Upvotes: 0

Alen S Thomas
Alen S Thomas

Reputation: 1113

Basically, Dijkstra's can only be can be used to determine the shortest path in a given weighted graph from one source node to every other node within the same graph data structure, provided that the nodes are reachable from the source node. The algorithm runs until it visits all the vertices in the graph. The shortest path is continuously looked up and updated.

Maybe this link will be helpful for a better understanding the algorithm itself. https://medium.com/basecs/finding-the-shortest-path-with-a-little-help-from-dijkstra-613149fbdc8e

Upvotes: 1

Related Questions