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
|
//Dijkstra without Heaps
#include <chrono>
#include <iostream>
#include <climits>
using namespace std;
using namespace std::chrono;
// Number of vertices in the graph
#define V 22
//Name: name of your function: print2user()
//Description: purpose of the function: Prints the nodes and distance from the source to those nodes.
//Input: array distance[]
//Output: Prints the nodes and distance from the source to those nodes.
void print2user(int distance[], int Source)
{
cout << "Vertex Distance From Node " << Source << endl;
for (int i = 0; i < V; i++)
{
cout << i << " " << distance[i] << endl;
}
}
//Name: name of your function: minimumDistance()
//Description: purpose of the function: Finds the vertex with minimum value of edge from a list (ShortestPathList) of vertices that hasn't been visited yet.
//Input: array distance[] and array ShortestPathList[]
//Output: returns the index with the minimum distance, or, returns the cheapest edge.
int minimumDistance(int distance[], bool ShortestPathList[])
{
//initialise everything to Infinity, aka INT_MAX.
int minimum = INT_MAX, minimumIndex;
for (int i = 0; i < V; i++)
{
//if the node has not been visited yet, aka 'false' and its distance is less than the current distance, update it.
if (ShortestPathList[i] == false && distance[i] <= minimum)
{
minimum = distance[i];
minimumIndex = i;
}
}
return minimumIndex;
}
//Name: name of your function: findMinimumPath()
//Description: purpose of the function: Finds the minimum path from a source node to all nodes.
//Input: 2D array graph[V][V] and Source node.
//Output: Prints the distance from the source to all nodes. User can specify what the source is, in this case it's 20.
void findMinimumPath(int graph[V][V], int Source)
{
//this array holds the distance from the source to all nodes.
int distance[V];
//this array will be true if the vertex is included in the shortest path from source to all nodes.
bool ShortestPathList[V];
//initialise everything to INT_MAX and false.
for (int i = 0; i < V; i++)
{
distance[i] = INT_MAX, ShortestPathList[i] = false;
}
//distance from source to itself is always 0 because there are no self loops.
distance[Source] = 0;
//this for loop look for the vertex with the minimum distance from the list of vertices that haven't been visited yet.
//V - 1 because we don't count the source.
for (int i = 0; i < V - 1; i++)
{
//now the minimum index returned from the function minimumDistance() is held in CurrentVertex
int CurrentVertex = minimumDistance(distance, ShortestPathList);
//after the vertex has been visited, mark it as visited aka true.
ShortestPathList[CurrentVertex] = true;
//this for loop will update the distance of the neighbours of the picked vertex, aka: CurrentVertex.
for (int i = 0; i < V; i++)
{
//update distance[i] only if: vertex is not in ShortestPathList, and there is an edge from CurrentVertex to i and the total cost of that path (source -> i) thru CurrentVertex is < current value in distance[i]
if (!ShortestPathList[i] && graph[CurrentVertex][i] && distance[CurrentVertex] != INT_MAX && distance[CurrentVertex] + graph[CurrentVertex][i] < distance[i])
{
distance[i] = distance[CurrentVertex] + graph[CurrentVertex][i];
}
}
}
//print solution
print2user(distance, Source);
}
int main()
{
//important note: I increased every weight by 1 to avoid having 0s as distances, because in the code, a 0 means no connection.
int graph[V][V] =
{ { 0, 11, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 11, 0, 2, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 2, 0, 8, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 8, 0, 6, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 6, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2 },
{ 8, 0, 0, 0, 0, 0, 6, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 4, 0, 0, 0, 6, 0, 11, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 11, 0, 2, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 5, 0, 0, 0, 2, 0, 9, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 2, 0, 0, 0, 9, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 5 },
{ 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 7, 0, 0, 0, 9, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 11, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 11, 0, 11, 0, 0, 0, 4, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 11, 0, 0, 0, 0, 0, 5, 0, 5 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 5, 0, 11, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 1, 0, 11, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 11, 0, 0, 4 },
{ 1, 0, 0, 0, 0, 8, 0, 0, 0, 0, 4, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
};
//find solution and print it
high_resolution_clock::time_point t1 = high_resolution_clock::now();
findMinimumPath(graph, 20);
high_resolution_clock::time_point t2 = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(t2 - t1).count();
cout << "The program took: " << duration << " microseconds" << endl;
system("PAUSE");
return 0;
}
|
