-
Notifications
You must be signed in to change notification settings - Fork 8
/
dijkstraAlgo.cpp
106 lines (94 loc) · 2.62 KB
/
dijkstraAlgo.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
/// SHORTEST PATH, OF EACH NODE, FROM A GIVEN NODE *IN UNDIRECTED GRAPH*
///-> USING WEIGHTD ADJLIST
///->BFS like treversal
///->Minimize the distance
#include <bits/stdc++.h>
using namespace std;
// class tampleting
template <typename T>
class Giraff
{
public:
// adJList of WEIGHTED graph
// it has map of NODES to LIST of PAIR of AdjElements and WEIGHTS
unordered_map<T, vector<pair<T, T>>> adjList;
int size;
Giraff(int n)
{
size = n;
}
void add_edge(T u, T v, T w)
{
adjList[u].push_back(make_pair(v, w));
adjList[v].push_back(make_pair(u, w));
}
void display_graph()
{
for (auto i : adjList)
{
cout << endl;
cout << i.first << "->";
for (auto j : i.second)
{
cout << "[" << j.first << "," << j.second << "]; ";
}
}
}
/////////////The Dijkstra/////////////
vector<int> dijkstra(int source)
{
// step 1: Neet a SET of pair,Dist Vector
set<pair<int, int>> Q;
vector<int> distance(size, INT_MAX);
// step 2: start with the given node
distance[source] = 0;
Q.insert(make_pair(0, source));
while (!Q.empty())
{
// get and earase temp(front)
pair<int, int> temp = *(Q.begin());
Q.erase(Q.begin());
int currentNode = temp.second;
int currentDistance = temp.first;
for (auto i : adjList[currentNode])
{
int t = (currentDistance + i.second);
if (t < distance[i.first])
{
//check and rease previous pair if it exists
auto rec = Q.find(make_pair(distance[i.first], i.first));
if (rec != Q.end())
Q.erase(rec);
distance[i.first] = t;
Q.insert(make_pair(t, i.first));
}
}
}
//printing distances
cout << endl;
for (auto i : distance)
{
cout << i << " ";
}
return distance;
}
};
int main()
{
cout << "Give the map:";
// cout << "\n Number of edges: nodes";
int e = 19, n = 5, u, v, w;
// cin >> e >> n;
Giraff<int> G1(n);
for (int i = 0; i < e; i++)
{
cin >> u >> v >> w;
G1.add_edge(u, v, w);
}
G1.display_graph();
cout << endl;
G1.dijkstra(0);
///!!Run sucessfully!!
char a;
cin>>a;
}