Scribd
Upload
3 views1 page

Notes

The document outlines a step-by-step process for implementing Dijkstra's algorithm using a graph with node A as the source. It details the initialization of nodes, the relaxation process for neighboring nodes, and the sequence of visiting nodes based on the shortest path. The algorithm concludes once all nodes have been visited and their shortest paths determined.

Uploaded by

Shorya Mishra
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as ODT, PDF, TXT or read online on Scribd
3 views1 page

Notes

The document outlines a step-by-step process for implementing Dijkstra's algorithm using a graph with node A as the source. It details the initialization of nodes, the relaxation process for neighboring nodes, and the sequence of visiting nodes based on the shortest path. The algorithm concludes once all nodes have been visited and their shortest paths determined.

Uploaded by

Shorya Mishra
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as ODT, PDF, TXT or read online on Scribd

1. We will use the above graph as the input, with node A as the source.

2. First, we will mark all the nodes as unvisited.


3. We will set the path to 0 at node A and INFINITY for all the other nodes.
4. We will now mark source node A as visited and access its neighboring nodes.
Note: We have only accessed the neighboring nodes, not visited them.
5. We will now update the path to node B by 4 with the help of relaxation because the path to
node A is 0 and the path from node A to B is 4, and the minimum((0 + 4), INFINITY) is 4.
6. We will also update the path to node C by 5 with the help of relaxation because the path to
node A is 0 and the path from node A to C is 5, and the minimum((0 + 5), INFINITY) is 5.
Both the neighbors of node A are now relaxed; therefore, we can move ahead.
7. We will now select the next unvisited node with the least path and visit it. Hence, we will
visit node B and perform relaxation on its unvisited neighbors. After performing relaxation,
the path to node C will remain 5, whereas the path to node E will become 11, and the path to
node D will become 13.
8. We will now visit node E and perform relaxation on its neighboring nodes B, D, and F.
Since only node F is unvisited, it will be relaxed. Thus, the path to node B will remain as it
is, i.e., 4, the path to node D will also remain 13, and the path to node F will become 14 (8 +
6).
9. Now we will visit node D, and only node F will be relaxed. However, the path to node F
will remain unchanged, i.e., 14.
[Link] only node F is remaining, we will visit it but not perform any relaxation as all its
neighboring nodes are already visited.
[Link] all the nodes of the graphs are visited, the program will end.

You might also like