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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
#pragma once
#include <vector>
#include <unordered_set>
#include <queue>
#include <limits>
class WeightedGraph {
private:
class WeightedNode;
class WeightedEdge {
friend class WeightedGraph;
WeightedNode *mFirst, *mSecond;
double mWeight;
WeightedEdge(WeightedNode *first, WeightedNode *second, double weight)
: mFirst(first), mSecond(second), mWeight(weight) { }
bool operator<(const WeightedEdge &rhs) {
return mWeight < rhs.mWeight;
}
};
class WeightedNode {
friend class WeightedGraph;
int mIndex;
std::vector<WeightedEdge> mNeighbors;
WeightedNode(int index) : mIndex(index) {}
};
// for Dijkstra's algorithm.
class DijkstraDistance {
friend class WeightedGraph;
int mVertex;
double mCurrentDistance;
DijkstraDistance(int vertex, double distance) : mVertex(vertex), mCurrentDistance(distance) {}
bool operator<(const DijkstraDistance &rhs) {
return mCurrentDistance < rhs.mCurrentDistance;
}
};
std::vector<WeightedNode> mVertices;
// C++'s priority queue does not have a function to re-sort one element whose sort key has changed.
// Instead we do this (kind of hacky).
void RebuildQueue(std::priority_queue<DijkstraDistance> *q) {
std::make_heap(const_cast<DijkstraDistance*>(&q->top()),
const_cast<DijkstraDistance*>(&q->top()) + q->size());
}
public:
WeightedGraph(int vertices) {
for (int i = 0; i < vertices; i++) {
mVertices.emplace_back(i);
}
}
void AddEdge(int firstVertex, int secondVertex, double weight) {
WeightedNode &first = mVertices[firstVertex], &second = mVertices[secondVertex];
WeightedEdge edge(&first, &second, weight);
first.mNeighbors.push_back(edge);
}
/**
* Prints the graph to the console. Each vertex is printed on its own line,
* starting with the vertex's number (its index in the mVertices list), then
* a colon, then a sequence of pairs for each edge incident to the vertex.
* For each edge, print the number of the vertex at the opposite end of the
* edge, as well as the edge's weight.
*
* Example: in a graph with three vertices (0, 1, and 2), with edges from 0
* to 1 of weight 10, and from 0 to 2 of weight 20, printGraph() should print
*
* Vertex 0: (1, 10), (2, 20) Vertex 1: (0, 10) Vertex 2: (0, 20)
*/
void PrintGraph() {
}
/**
* Applies Prim's algorithm to build and return a minimum spanning tree for
* the graph. Start by constructing a new WeightedGraph with the same number
* of vertices as this graph. Then apply Prim's algorithm. Each time an edge
* is selected by Prim's, add an equivalent edge to the other graph. When
* complete, return the new graph, which is the minimum spanning tree.
*
* @return an UnweightedGraph representing this graph's minimum spanning
* tree.
*/
WeightedGraph GetMinimumSpanningTree() {
WeightedGraph temp(mVertices.size());
// TODO: build and return the MST as the variable "temp".
return temp;
}
/**
* Applies Dijkstra's algorithm to compute the shortest paths from a source
* vertex to all other vertices in the graph. Returns an array of path
* lengths; each value in the array gives the length of the shortest path
* from the source vertex to the corresponding vertex in the array.
*
* To use this function in main, call:
* std::vector<double> shortestPaths = mygraph.GetShortestPathsFrom(1);
*/
std::vector<double> GetShortestPathsFrom(int source) {
// TODO: apply Dijkstra's algorithm and return the distances array.
// This queue is used to select the vertex with the smallest "d" value
// so far.
// Each time a "d" value is changed by the algorithm, the corresponding
// DijkstraDistance object needs to be removed and then re-added to
// the queue so its position updates.
std::priority_queue<DijkstraDistance> vertexQueue;
// Initialization: set the distance of the source node to 0, and all
// others to infinity. Add all distances to the vertex queue.
std::vector<DijkstraDistance> distances(mVertices.size());
distances[source] = DijkstraDistance(source, 0);
for (int i = 0; i < distances.size(); i++) {
if (i != source)
distances[i] = DijkstraDistance(i, std::numeric_limits<int>::max()); // set all others = infinity
vertexQueue.push(distances[i]);
}
while (vertexQueue.size() > 0) { // Q not empty
// Finish the algorithm.
// remove node u from Q
// for each child v of u:
for () {
// reminder: c(a, b) = cost of edge (a, b)
// let len = d(u) + c(u, v)
int len = distances[source] + DijkstraDistance(source, mNeighbors);
// if len < d(v):
if (len < distances[mNeighbors]) {
// new shortest path to v found via u
// set p(v) = u
// set d(v) = len
distances[mNeighbors] = len;
}
}
}
std::vector<double> answers;
// Fill in this vector with your answers.
return answers;
}
};
|
