CODEWITHSUNDEEP
algorithmdijkstradirected-graphundirected-graph
K22
K22

Reputation: 147

Trying to understand Dijkstra's Algorithm

I am trying to better understand Dijkstra's Algorithm. I have attached an image of the algorithm that is in my textbook. The pseudocode shows the input is an undirected graph, but is the algorithm any different for a directed graph? I have looked up the algorithms with the input of a directed graph and I did not identify any differences. 

Algorithm ShortestPath(G, v)

Input: A simple undirected weighted graph G with nonnegative edge weights and a distinguished vertex v of G

Output: A label D[u], for each vertex u of G, such that D[u] is the length of a shortest path from v to u in G

Initialize D[v]<--0 and D[u]<--+infinity for each vertex u != v.

Let priority queue Q contain all the vertices of G using the D labels as keys.

while Q is not empty do

    {pull a new vertex u into the cloud}

u<-- Q.removeMin()

for each vertex z adjacent to u such that z is in Q do

    {preform the relaxation procedure on edge (u,z)}

    if D[u]+w((u,z))<D[z] then

         D[z]<-- D[u]+w((u,z))

         change to D[z] the of vertex z in Q

return the label D[u] of each vertex u

Dijkstra's Algorithm

Upvotes: 0

Views: 624

Answers (1)

marvel308
marvel308

Reputation: 10458

You can use Dijkstra's algorithm in both directed and undirected graphs, because you simply add edges into the PriorityQueue when you have an edge to travel to from your adjacency list. For example, if one of my nodes has an edge from A to B of weight 3, then if it's directed from B I won't be able to add the edge back into A, while from A I could add it to B.

Like the other answers, make sure you do not confuse it with weights. Dijkstra's algorithm runs on positive weighed graphs, otherwise the priority queue would be useless.

Upvotes: 1

Related Questions