-
Notifications
You must be signed in to change notification settings - Fork 0
/
Digraph.h
114 lines (103 loc) · 3.37 KB
/
Digraph.h
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
110
111
112
113
114
#include <map>
#include <vector>
#include <queue>
#include <iostream>
#include <iomanip>
using namespace std;
template<typename DataType>
class Digraph {
public:
DataType data(int k) const;
void read(istream &in);
void display(ostream &out);
vector<int> shortestPath(int start, int destination);
private:
class VertesInfo {
public:
DataType data;
map<int, int> adjacencyList;
};
vector<VertesInfo> myAdjacencyLists;
};
template<typename DataType>
DataType Digraph<DataType>::data(int k) const {
return myAdjacencyLists[k].data;
}
template<typename DataType>
void Digraph<DataType>::read(istream &in) {
Digraph<DataType>::VertesInfo vi;
int n, vertex, dis, m;
in >> m;
while (m--) {
in >> vi.data;
in >> n;
map<int, int> adjList;
for (int i = 0; i < n; ++i) {
in >> vertex >> dis;
adjList.insert(pair<int, int>(vertex, dis));
}
vi.adjacencyList = adjList;
myAdjacencyLists.push_back(vi);
}
}
template<typename DataType>
void Digraph<DataType>::display(ostream &out) {
out << "Adjacency-List Representation: \n";
for (int i = 0; i < myAdjacencyLists.size(); ++i) {
if (myAdjacencyLists[i].adjacencyList.empty()) {
out << i << ": " << myAdjacencyLists[i].data << endl;
continue;
}
out << i << ": " << myAdjacencyLists[i].data << "-";
for (auto iter = myAdjacencyLists[i].adjacencyList.begin();
iter != myAdjacencyLists[i].adjacencyList.end(); ++iter) {
if (iter == myAdjacencyLists[i].adjacencyList.begin()) {
out << myAdjacencyLists[iter->first].data;
} else {
out << " " << myAdjacencyLists[iter->first].data;
}
out << endl;
}
}
}
template<typename DataType>
vector<int> Digraph<DataType>::shortestPath(int start, int destination) {
int n = myAdjacencyLists.size();
vector<int> distLabel(n, -1), predLabel(n, -1);
vector<bool> flag(n, false);
distLabel[start] = 0;
int distance, vertex;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<> > vertexQueue;
vertexQueue.push(pair<int, int>(0, start));
while (!flag[destination] && !vertexQueue.empty()) {
if (flag[vertexQueue.top().second]) {
vertexQueue.pop();
continue;
}
vertex = vertexQueue.top().second;
distance = vertexQueue.top().first;
flag[vertex] = true;
vertexQueue.pop();
for (auto iter = myAdjacencyLists[vertex].adjacencyList.begin();
iter != myAdjacencyLists[vertex].adjacencyList.end(); ++iter) {
if (!flag[iter->first] &&
(predLabel[iter->first] < 0 || distLabel[iter->first] > distance + iter->second)) {
distLabel[iter->first] = distance + iter->second;
predLabel[iter->first] = vertex;
vertexQueue.push(pair<int, int>(distance + iter->second, iter->first));
}
}
}
vector<int> path;
if (distLabel[destination] < 0) {
cout << "Destination not reachable from start vertex\n";
} else {
path.push_back(destination);
int d = destination;
while (predLabel[d] != -1) {
path.push_back(predLabel[d]);
d = predLabel[d];
}
}
return path;
}