Question about Dijkstra's algorithm implementation on Wikipedia -


function dijkstra(graph, source):     each vertex v in graph:            // initializations         dist[v] := infinity ;              // unknown distance function source v         previous[v] := undefined ;         // previous node in optimal path source     end ;     dist[source] := 0 ;                    // distance source source     q := set of nodes in graph ;     // nodes in graph unoptimized - in q     while q not empty:                  // main loop         u := vertex in q smallest dist[] ;         if dist[u] = infinity:             break ;                        // remaining vertices inaccessible source         fi ;         remove u q ;         each neighbor v of u:          // v has not yet been removed q.             alt := dist[u] + dist_between(u, v) ;             if alt < dist[v]:              // relax (u,v,a)                 dist[v] := alt ;                 previous[v] := u ;             fi ;         end ;     end while ;     return dist[] ; end dijkstra. 

the above algorithm has been mentioned in wikipedia dijkstra shortest path. not able understand here that, while have set distances vertices infinity [line number 3], @ line 9 assigning u := vertex in q smallest dist[] since distances infinite (as set in line number 3) how can there smallest distance?

in line 6 says dist[source] := 0 makes 1 of distances non-infinite. once removed, successive iterations of loop set dist[v] := alt, creating more non-infinite distances.


Comments

Popular posts from this blog

python - Scipy curvefit RuntimeError:Optimal parameters not found: Number of calls to function has reached maxfev = 1000 -

c# - How to add a new treeview at the selected node? -

java - netbeans "Please wait - classpath scanning in progress..." -