-
Notifications
You must be signed in to change notification settings - Fork 0
/
dijkstra_algorithm.cpp
109 lines (90 loc) · 2.84 KB
/
dijkstra_algorithm.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
struct Edge {
int destination;
int weight;
};
struct Node {
int id;
vector<Edge> neighbors;
};
class Graph {
public:
unordered_map<int, Node> nodes;
void addEdge(int source, int destination, int weight) {
nodes[source].id = source;
nodes[destination].id = destination;
nodes[source].neighbors.push_back({destination, weight});
}
pair<int, vector<int>> dijkstra(int start, int end) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
unordered_map<int, int> distance;
unordered_map<int, int> previous;
for (const auto& pair : nodes) {
int node = pair.first;
distance[node] = numeric_limits<int>::max();
previous[node] = -1;
}
distance[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
int current = pq.top().second;
pq.pop();
for (const auto& neighbor : nodes[current].neighbors) {
int new_distance = distance[current] + neighbor.weight;
if (new_distance < distance[neighbor.destination]) {
distance[neighbor.destination] = new_distance;
previous[neighbor.destination] = current;
pq.push({new_distance, neighbor.destination});
}
}
}
vector<int> path;
int current = end;
while (current != -1) {
path.push_back(current);
current = previous[current];
}
reverse(path.begin(), path.end());
return {distance[end], path};
}
void outputGraph() {
cout << "digraph G {" << endl;
for (const auto& pair : nodes) {
int source = pair.first;
for (const auto& neighbor : nodes[source].neighbors) {
int destination = neighbor.destination;
int weight = neighbor.weight;
cout << source << " -> " << destination << " [label=\"" << weight << "\"];" << endl;
}
}
cout << "}" << endl;
}
};
int main() {
Graph graph;
graph.addEdge(1, 2, 5);
graph.addEdge(1, 3, 2);
graph.addEdge(2, 4, 1);
graph.addEdge(3, 4, 6);
graph.addEdge(4, 5, 3);
cout << "Generated DOT representation of the graph:" << endl;
graph.outputGraph();
int start, end;
cout << "Enter the starting node: ";
cin >> start;
cout << "Enter the ending node: ";
cin >> end;
auto result = graph.dijkstra(start, end);
cout << "Cost of the shortest path: " << result.first << endl;
cout << "Shortest path: ";
for (int node : result.second) {
cout << node << " ";
}
return 0;
}