[ dalibor_zdravkovic @ 18.03.2009. 02:05 ] @
| Kako implemntirati sledeci pseudo kod u C++ koji simulira Dijkstra algoritam za pronalazenje najkracih puteva u grafu? Cvor grafa bi bio implemtiran klasom sa imenom "nod"; Program bi trebao da za ulaz uzima elemente grafa (cvorove, grane, i tezine grana) kao i cvor za koga se traze najkraci putevi do drugih cvorova u grafu (startni cvor) a kao rezultat bi trebalo da za svaki cvor daje parove (cvor,tezina). Za vise informacija pogledati Dijkstra Algorithm. Code: 1 function Dijkstra(Graph, source): 2 for each vertex v in Graph: // Initializations 3 dist[v] := infinity // Unknown distance function from source to v 4 previous[v] := undefined // Previous node in optimal path from source 5 dist[source] := 0 // Distance from source to source 6 Q := the set of all nodes in Graph // All nodes in the graph are unoptimized - thus are in Q 7 while Q is not empty: // The main loop 8 u := vertex in Q with smallest dist[] 9 remove u from Q 10 for each neighbor v of u: // where v has not yet been removed from Q. 11 alt := dist[u] + dist_between(u, v) // be careful in 1st step - dist[u] is infinity yet 12 if alt < dist[v] // Relax (u,v,a) 13 dist[v] := alt 14 previous[v] := u 15 return previous[] |