Write a program to perform the following in C++: 1)Implement Dijkstra’s Algorith
ID: 3919210 • Letter: W
Question
Write a program to perform the following in C++:
1)Implement Dijkstra’s Algorithm .
2)Read a graph data file. Each line contains weighted edge: “vertex, vertex, weight”
3)Using the implemented algorithm, find the shortest-paths tree from vertex M.
4)Report the shortest-paths tree from vertex M and distance to each other vertex.
graph.txt:
A,J,91
A,H,86
A,B,38
A,N,37
A,L,100
A,V,64
A,S,84
A,M,9
A,W,54
A,K,46
B,J,27
B,V,93
B,H,40
B,G,49
B,F,94
B,N,95
B,C,45
B,Z,42
B,L,15
C,Q,14
C,W,10
C,L,87
C,R,77
C,N,92
C,S,79
C,T,3
C,D,60
C,J,43
D,P,26
D,W,12
D,K,21
D,Q,5
D,V,75
D,T,59
D,J,2
D,R,11
F,J,63
F,X,72
F,L,88
F,G,51
F,V,61
F,P,39
F,M,69
F,W,65
G,N,76
G,X,13
G,Z,56
G,H,82
G,Q,32
G,W,20
G,V,18
H,Z,74
H,P,85
H,L,62
H,M,44
H,K,25
H,J,98
H,R,19
J,V,31
J,M,50
J,S,57
J,Q,17
J,T,22
J,P,68
K,T,67
K,L,81
K,M,55
K,P,52
K,S,83
K,X,41
L,R,36
L,N,30
L,T,53
L,S,23
L,Q,66
M,S,6
M,Q,29
M,N,71
M,R,8
M,T,96
N,T,16
N,R,78
N,Q,73
N,V,24
P,Z,28
P,W,48
P,Q,7
P,T,47
Q,W,99
Q,S,1
Q,Z,89
R,V,70
R,X,35
R,S,33
S,T,34
S,X,90
T,X,4
T,W,58
V,X,80
W,Z,97
Explanation / Answer
Dijkstra's algorithm allows to find the shortest path between any two vertices of a weighted graph.
//c++ code
#include <iostream>
#include <vector>
#define INT_MAX 10000000
using namespace std;
void DijkstrasTest();
int main()
{
DijkstrasTest();
return 0;
}
class Node;
class Edge;
void Dijkstras();
vector<Node*>* AdjacentRemainingNodes(Node* node);
Node* ExtractSmallest(vector<Node*>& nodes);
int Distance(Node* node1, Node* node2);
bool Contains(vector<Node*>& nodes, Node* node);
void PrintShortestRouteTo(Node* destination);
vector<Node*> nodes;
vector<Edge*> edges;
class Node
{
public:
Node(char id)
: id(id), previous(NULL), distanceFromStart(INT_MAX)
{
nodes.push_back(this);
}
public:
char id;
Node* previous;
int distanceFromStart;
};
class Edge
{
public:
Edge(Node* node1, Node* node2, int distance)
: node1(node1), node2(node2), distance(distance)
{
edges.push_back(this);
}
bool Connects(Node* node1, Node* node2)
{
return (
(node1 == this->node1 &&
node2 == this->node2) ||
(node1 == this->node2 &&
node2 == this->node1));
}
public:
Node* node1;
Node* node2;
int distance;
};
///////////////////
void DijkstrasTest()
{
Node* a = new Node('a');
Node* b = new Node('b');
Node* c = new Node('c');
Node* d = new Node('d');
Node* f = new Node('f');
Node* g = new Node('g');
Node* h = new Node('h');
Node* j = new Node('j');
Node* k = new Node('k');
Node* l = new Node('l');
Node* m = new Node('m');
Node* n = new Node('n');
Node* p = new Node('p');
Node* q = new Node('q');
Node* r = new Node('r');
Node* s = new Node('s');
Node* t = new Node('t');
Node* v = new Node('v');
Node* w = new Node('w');
Node* x = new Node('x');
Node* z = new Node('z');
Edge* e1 = new Edge(a, j, 91);
Edge* e2 = new Edge(a, h, 86);
Edge* e3 = new Edge(a, b, 38);
Edge* e4 = new Edge(a, n, 37);
Edge* e5 = new Edge(a, l, 100);
Edge* e6 = new Edge(a, v, 64);
Edge* e7 = new Edge(a, s, 84);
Edge* e8 = new Edge(a, m, 9);
Edge* e9 = new Edge(a, w, 54);
Edge* e10 = new Edge(a, k, 46);
Edge* e11 = new Edge(b, j, 27);
Edge* e12 = new Edge(b, v, 93);
Edge* e13 = new Edge(b, h, 40);
Edge* e14 = new Edge(b, g, 49);
Edge* e15 = new Edge(b, f, 94);
Edge* e16 = new Edge(b, n, 95);
Edge* e17 = new Edge(b, c, 45);
Edge* e18 = new Edge(b, z, 42);
Edge* e19 = new Edge(b, l, 15);
Edge* e20 = new Edge(c, q, 14);
Edge* e21 = new Edge(c, w, 10);
Edge* e22 = new Edge(c, l, 87);
Edge* e23 = new Edge(c, r, 77);
Edge* e24 = new Edge(c, n, 92);
Edge* e25 = new Edge(c, s, 79);
Edge* e26 = new Edge(c, t, 3);
Edge* e27 = new Edge(c, d, 60);
Edge* e28 = new Edge(c, j, 43);
Edge* e29 = new Edge(d, p, 26);
Edge* e30 = new Edge(d, w, 12);
Edge* e31 = new Edge(d, k, 21);
Edge* e32 = new Edge(d, q, 5);
Edge* e33 = new Edge(d, v, 75);
Edge* e34 = new Edge(d, t, 59);
Edge* e35 = new Edge(d, j, 2);
Edge* e36 = new Edge(d, r, 11);
Edge* e37 = new Edge(f, j, 63);
Edge* e38 = new Edge(f, x, 72);
Edge* e39 = new Edge(f, l, 88);
Edge* e40 = new Edge(f, g, 51);
Edge* e41 = new Edge(f, v, 61);
Edge* e42 = new Edge(f, p, 39);
Edge* e43 = new Edge(f, m, 69);
Edge* e44 = new Edge(f, w, 65);
Edge* e45 = new Edge(g, n, 76);
Edge* e46 = new Edge(g, x, 13);
Edge* e47 = new Edge(g, z, 56);
Edge* e48 = new Edge(g, h, 82);
Edge* e49 = new Edge(g, q, 32);
Edge* e50 = new Edge(g, w, 20);
Edge* e51 = new Edge(g, v, 18);
Edge* e52 = new Edge(h, z, 74);
Edge* e53 = new Edge(h, p, 85);
Edge* e54 = new Edge(h, l, 62);
Edge* e55 = new Edge(h, m, 44);
Edge* e56 = new Edge(h, k, 25);
Edge* e57 = new Edge(h, j, 98);
Edge* e58 = new Edge(h, r, 19);
Edge* e59 = new Edge(j, v, 31);
Edge* e60 = new Edge(j, m, 50);
Edge* e61 = new Edge(j, s, 57);
Edge* e62 = new Edge(j, q, 17);
Edge* e63 = new Edge(j, t, 22);
Edge* e64 = new Edge(j, p, 68);
Edge* e65 = new Edge(k, t, 67);
Edge* e66 = new Edge(k, l, 81);
Edge* e67 = new Edge(k, m, 55);
Edge* e68 = new Edge(k, p, 52);
Edge* e69 = new Edge(k, s, 83);
Edge* e70 = new Edge(k, x, 41);
Edge* e71 = new Edge(l, r, 36);
Edge* e72 = new Edge(l, n, 30);
Edge* e73 = new Edge(l, t, 53);
Edge* e74 = new Edge(l, s, 23);
Edge* e75 = new Edge(l, q, 66);
Edge* e76 = new Edge(m, s, 6);
Edge* e77 = new Edge(m, q, 29);
Edge* e78 = new Edge(m, n, 71);
Edge* e79 = new Edge(m, r, 8);
Edge* e80 = new Edge(m, t, 96);
Edge* e81 = new Edge(n, t, 16);
Edge* e82 = new Edge(n, r, 78);
Edge* e83 = new Edge(n, q, 73);
Edge* e84 = new Edge(n, v, 24);
Edge* e85 = new Edge(p, z, 28);
Edge* e86 = new Edge(p, w, 48);
Edge* e87 = new Edge(p, q, 7);
Edge* e88 = new Edge(p, t, 47);
Edge* e89 = new Edge(q, w, 99);
Edge* e90 = new Edge(q, s, 1);
Edge* e91 = new Edge(q, z,89);
Edge* e92 = new Edge(r, v, 70);
Edge* e93 = new Edge(r, x, 35);
Edge* e94 = new Edge(r, s, 33);
Edge* e95 = new Edge(s, t, 34);
Edge* e96 = new Edge(s, x, 90);
Edge* e97 = new Edge(t, x, 4);
Edge* e98 = new Edge(t, w, 58);
Edge* e99 = new Edge(v, x, 80);
Edge* e100 = new Edge(w, z, 97);
m->distanceFromStart = 0; // set start node
Dijkstras();
PrintShortestRouteTo(f);
}
///////////////////
void Dijkstras()
{
while (nodes.size() > 0)
{
Node* smallest = ExtractSmallest(nodes);
vector<Node*>* adjacentNodes =
AdjacentRemainingNodes(smallest);
const int size = adjacentNodes->size();
for (int i=0; i<size; ++i)
{
Node* adjacent = adjacentNodes->at(i);
int distance = Distance(smallest, adjacent) +
smallest->distanceFromStart;
if (distance < adjacent->distanceFromStart)
{
adjacent->distanceFromStart = distance;
adjacent->previous = smallest;
}
}
delete adjacentNodes;
}
}
// Find the node with the smallest distance,
// remove it, and return it.
Node* ExtractSmallest(vector<Node*>& nodes)
{
int size = nodes.size();
if (size == 0) return NULL;
int smallestPosition = 0;
Node* smallest = nodes.at(0);
for (int i=1; i<size; ++i)
{
Node* current = nodes.at(i);
if (current->distanceFromStart <
smallest->distanceFromStart)
{
smallest = current;
smallestPosition = i;
}
}
nodes.erase(nodes.begin() + smallestPosition);
return smallest;
}
// Return all nodes adjacent to 'node' which are still
// in the 'nodes' collection.
vector<Node*>* AdjacentRemainingNodes(Node* node)
{
vector<Node*>* adjacentNodes = new vector<Node*>();
const int size = edges.size();
for(int i=0; i<size; ++i)
{
Edge* edge = edges.at(i);
Node* adjacent = NULL;
if (edge->node1 == node)
{
adjacent = edge->node2;
}
else if (edge->node2 == node)
{
adjacent = edge->node1;
}
if (adjacent && Contains(nodes, adjacent))
{
adjacentNodes->push_back(adjacent);
}
}
return adjacentNodes;
}
// Return distance between two connected nodes
int Distance(Node* node1, Node* node2)
{
const int size = edges.size();
for(int i=0; i<size; ++i)
{
Edge* edge = edges.at(i);
if (edge->Connects(node1, node2))
{
return edge->distance;
}
}
return -1; // should never happen
}
// Does the 'nodes' vector contain 'node'
bool Contains(vector<Node*>& nodes, Node* node)
{
const int size = nodes.size();
for(int i=0; i<size; ++i)
{
if (node == nodes.at(i))
{
return true;
}
}
return false;
}
///////////////////
void PrintShortestRouteTo(Node* destination)
{
Node* previous = destination;
cout << "Distance from start: "
<< destination->distanceFromStart << endl;
while (previous)
{
cout << previous->id << " ";
previous = previous->previous;
}
cout << endl;
}
// these two not needed
vector<Edge*>* AdjacentEdges(vector<Edge*>& Edges, Node* node);
void RemoveEdge(vector<Edge*>& Edges, Edge* edge);
vector<Edge*>* AdjacentEdges(vector<Edge*>& edges, Node* node)
{
vector<Edge*>* adjacentEdges = new vector<Edge*>();
const int size = edges.size();
for(int i=0; i<size; ++i)
{
Edge* edge = edges.at(i);
if (edge->node1 == node)
{
cout << "adjacent: " << edge->node2->id << endl;
adjacentEdges->push_back(edge);
}
else if (edge->node2 == node)
{
cout << "adjacent: " << edge->node1->id << endl;
adjacentEdges->push_back(edge);
}
}
return adjacentEdges;
}
void RemoveEdge(vector<Edge*>& edges, Edge* edge)
{
vector<Edge*>::iterator it;
for (it=edges.begin(); it<edges.end(); ++it)
{
if (*it == edge)
{
edges.erase(it);
return;
}
}
}
output
Distance from start: 53 // from node m the shortest distance is 53
f p q s m // shortest path from m is f-p-q-s
I SPENT MUCH TIME ON THIS PROGRAM. COMMENTS ARE WELCOME...DO LIKE IF U LIKE.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.