Algorithms : complete 03-algorithms_on_graphs 04-paths_in_graphs

1 files changed, 29 insertions, 6 deletions

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 <iostream>
+#include <limits>
 #include <vector>
 #include <queue>
 
 using std::vector;
-using std::queue;
-using std::pair;
 using std::priority_queue;
 
-int distance(vector<vector<int> > &adj, vector<vector<int> > &cost, int s, int t) {
-  //write your code her
-  return -1;
+int distance(vector<vector<int> > &adj, vector<vector<int> > &cost, int s, int t)
+{
+    vector<int> dists(adj.size(), std::numeric_limits<int>::max());
+
+    std::priority_queue<int, std::vector<int>, std::greater<int>> 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<int>::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';
 }