CODEWITHSUNDEEP
algorithmgraph-algorithmdijkstra
Y N
Y N

Reputation: 841

Dijkstra's and Prim's algorithm

as I see Dijkstra's and Prim's algorithms are amost the same. Here is the pseudocode from wikipedia, I'll explain the poinf of my confusion.

1  function Dijkstra(Graph, source):
2      dist[source] ← 0                                    // Initialization
3
4      create vertex set Q
5
6      for each vertex v in Graph:           
7          if v ≠ source
8              dist[v] ← INFINITY                          // Unknown distance from source to v
9              prev[v] ← UNDEFINED                         // Predecessor of v
10
11         Q.add_with_priority(v, dist[v])
12
13
14     while Q is not empty:                              // The main loop
15         u ← Q.extract_min()                            // Remove and return best vertex
16         for each neighbor v of u:                      // only v that is still in Q
17             alt ← dist[u] + length(u, v) 
18             if alt < dist[v]
19                 dist[v] ← alt
20                 prev[v] ← u
21                 Q.decrease_priority(v, alt)
22
23     return dist[], prev[]

Prim's algorithm is almost the same, for convenience, I'll just change the loop that starts in 14th line

14     while Q is not empty:                              
15         u ← Q.extract_min()                            
16         for each neighbor v of u:                      
17             if v ∈ Q and length(u, v) < cost[v]
18                 cost[v] ← length(u, v)
19                 prev[v] ← u
20                 Q.decrease_priority(v, length(u, v))

There are two changes, the first is replacing dist[] with cost[] and as I understand this is related to the fact that algorithms solve different problems. The second one is obscure for me, namely the absence of if v ∈ Q this condition in Dijkstra's algorithm. I don't really get why we CAN return to the set of visited vertices in Prim's algorithm and this CANNOT happen in Dijkstra's algorithm.

Upvotes: 1

Views: 513

Answers (3)

arboreal84
arboreal84

Reputation: 2154

Dijkstra and Prim algorithms are very similar.

The difference is:

  • Prim's algorithm: Closest vertex to a minimum spanning tree via an undirected edge

  • Dijsktra's algorithm: Closest vertex to a source via a directed path

Source: Algorithms by Sedgewick & Wayne

Upvotes: 0

Aasmund Eldhuset
Aasmund Eldhuset

Reputation: 37950

In Dijkstra, we compute alt ← dist[u] + length(u, v) and set dist[v] to alt if alt is smaller than the current value of dist[v]. alt represents the distance from the start node to v if we go via u. However, u is the node that was just taken out of Q, and so, its distance from the start node is greater than or equal to all other nodes that have previously been taken out of Q. Because Dijkstra requires all edge weights to be nonnegative, alt is guaranteed to be greater than or equal to dist[v] if v is not in Q since it is the sum of dist[u] and length(u, v), and so it won't pass the condition in the if. In other words, if v is not in Q, u will be a detour relative to the path we already have to v.

Upvotes: 2

earliest
earliest

Reputation: 11

Not sure if I got your idea right. For both Dijkstra and prims algorithms, we should only deal with the vertex in the Q. For the Dijkstra algorithm, the pseudo code may not explicitly check if current vertice is still in Q, but it commented as "only v that is still in Q"

 for each neighbor v of u:                      // only v that is still in Q

I assume they means the same thing as x ∈ Q

17             if x ∈ Q and length(u, v) < cost[v]

if the x here represents "v" in line 16.

Upvotes: 1

Related Questions