Починил алгоритм Дейкстры

2 files changed, 9 insertions, 0 deletions

diff --git a/graphs-algo/Makefile b/graphs-algo/Makefile
index 7cdaf2a..5343597 100644
--- a/graphs-algo/Makefile
+++ b/graphs-algo/Makefile
@@ -9,6 +9,8 @@ test1: task1
 	@printf "Answer: \n"
 	@printf "4\n4\n1 2 1\n2 3 5\n3 4 1\n4 1 2\n2\n3" | ./task.out
 	@printf "Answer: \n"
+	@printf "3\n1\n1 2 1\n1 2" | ./task.out
+	@printf "Answer: \n"
 
 task2:
 	$(COMPILE) -o task.out task2.cpp
diff --git a/graphs-algo/task1.cpp b/graphs-algo/task1.cpp
index cd96c72..d6d2a83 100644
--- a/graphs-algo/task1.cpp
+++ b/graphs-algo/task1.cpp
@@ -2,6 +2,7 @@
 #include<vector>
 #include<algorithm>
 #include<iomanip>
+#include<stdio.h>
 
 using namespace std;
 
@@ -74,6 +75,7 @@ graph dijkstra(graph g, int n)
                     v = p;
                 }
             }
+            if (v == -1) continue;
             u[s][v] = 1;
 
             // Производим релаксации
@@ -103,6 +105,11 @@ vector<int> backtrack(graph paths, int start, int end)
     {
         path.push_back(cur);
         cur = paths[start][cur];
+        if (cur == -1)
+        {
+            path.clear();
+            return path;
+        }
     }
     path.push_back(start);
     reverse(path.begin(), path.end());