From f12e0947b27d5d66983d9ce2f0ad2732fbb373c9 Mon Sep 17 00:00:00 2001 From: Jérémy Zurcher Date: Sun, 13 Nov 2016 23:14:19 +0100 Subject: Algorithms : complete 03-algorithms_on_graphs 04-paths_in_graphs --- .../04-paths_in_graphs/01-dijkstra/dijkstra.cpp | 35 ++++++++++++++++++---- 1 file changed, 29 insertions(+), 6 deletions(-) (limited to '03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra') diff --git a/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/dijkstra.cpp b/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/dijkstra.cpp index 757a6c6..7b852e5 100644 --- a/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/dijkstra.cpp +++ b/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/dijkstra.cpp @@ -1,15 +1,38 @@ #include +#include #include #include using std::vector; -using std::queue; -using std::pair; using std::priority_queue; -int distance(vector > &adj, vector > &cost, int s, int t) { - //write your code her - return -1; +int distance(vector > &adj, vector > &cost, int s, int t) +{ + vector dists(adj.size(), std::numeric_limits::max()); + + std::priority_queue, std::greater> pq; + + dists[s] = 0; + pq.push(s); + + while(!pq.empty()) { + int n = pq.top(); + int dist = dists[n]; + /* std::cout << " pop: " << n + 1 << " : " << dist << std::endl; */ + pq.pop(); + + for (int i = 0; i < adj[n].size(); i++) { + int a = adj[n][i]; + int nd = dist + cost[n][i]; + if (dists[a] > nd) { + dists[a] = nd; + /* std::cout << " push: " << a + 1 << " : " << dists[a].first << std::endl; */ + pq.push(a); + } + } + } + + return (dists[t] == std::numeric_limits::max() ? -1 : dists[t]); } int main() { @@ -26,5 +49,5 @@ int main() { int s, t; std::cin >> s >> t; s--, t--; - std::cout << distance(adj, cost, s, t); + std::cout << distance(adj, cost, s, t) << '\n'; } -- cgit v1.2.3