KrozekGimVic / Grafi

Učenje algoritmov na grafih.
GNU General Public License v3.0
7 stars 0 forks source link

Add Dijkstra's shortest path algorithm. #6

Open jureslak opened 8 years ago

zigapk commented 8 years ago

Should dijkstra only return path length or the entire path?

jureslak commented 8 years ago

Hmm, I believe it is best to provide two overloads. As Dijsktra computes the shortest paths from one vertex to all the others (if not stopped early), it seems reasonable to provide an overload that does that, returning distances and previous map, telling for each node which index is the previous in the path.

pair<vector<double>, vector<int>> shortest_path_dijsktra(const graf_t& graf, int origin);

Another should find the shortest path from one vertex to another and break earlier than above, but also return the path, as it costs little more to provide that data.

pair<double, vector<int>> shortest_path_dijsktra(const graf_t& graf, int origin, int target);

This should be consistent with BellmanFord algorithm. @mucamaca