Advertisement
SVXX

Mysterious Graph Algorithm

Feb 15th, 2014
2,877
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
DOT 0.47 KB | None | 0 0
  1. Algorithm Weird(G, s)
  2.  
  3. 1 for v in V:
  4. 2    val[v] =
  5. 3 val[s]= 0
  6. 4 A = {} # A is a set
  7. 5 while A != V:
  8. 6    select vertex x not in A with minimum val[x]
  9. 7    A = A ∪ {x}
  10. 8    for each vertex y adjacent to x:
  11. 9       if val[x] + w(x, y) < val[y]:
  12. 10         val[y] = val[x] + w(x, y)
  13.  
  14. On applying this to the graph at http://imgur.com/a4CCo6O, I get the following result :-
  15. val = {0, 1, 5, 8, 13}
  16. Answer found on IRC #algorithms : This is Dijkstra's algorithm.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement