• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Dijkstra Shortest Path

jzh4n May 24th, 2019 99 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3.
4. int main() {
5.     int n;
6.
7.     std::cin >> n;
8.
9.     int *adjMatrix = new int [n * n];
10.
11.     for(int i = 0; i < n * n; ++i)
13.
14.     int (*visited)[2] = new int[n][2];
15.
16.     for(int i = 0; i < n; ++i)
17.         for(int j = 0; j < 2; ++j)
18.             visited[i][j] = -1;
19.
20.     visited[0][0] = 0;
21.
22.     for(int i = 0; i < n; ++i) {
23.         for(int j = i + 1; j < n; ++j) {
24.             if(adjMatrix[i * n + j]  > 0) {
25.                 if(visited[j][0] == -1 or visited[j][0] > visited[i][0]+ adjMatrix[i * n + j]) {
26.                     visited[j][0] = visited[i][0] + adjMatrix[i * n + j];
27.                     visited[j][1] = i;
28.                 }
29.             }
30.         }
31.     }
32.
33.     std::vector<int> path;
34.
35.     path.push_back(n - 1);
36.
37.     for(int i = n - 1; i;) {
38.         path.push_back(visited[i][1]);
39.
40.         i = visited[i][1];
41.     }
42.
43.     std::cout << "\n" << "Path: ";
44.
45.     int len = path.size();
46.
47.     for(int i = len - 1; i >= 0; --i) {
48.         if(i != len - 1 or i == 0)
49.             std::cout << " - ";
50.
51.         std::cout << path[i];
52.     }
53.
54.     return 0;
55. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top