Question

I wanted c++ program for the question

Problem 6 - Weighted Graph
In the vertex and edge structure defined below
Vertex        Edge   Vertex
SFO        2702   BOS
SFO        1846   ORD
ORD         867   BOS
ORD         742   JFK
JFK         189   BOS
SFO        1464   DFW
DFW         802   ORD
DFW        1123   MIA
MIA        1092   JFK
MIA        1258   BOS
SFO         339   LAX
LAX        1235   DFW
LAX        2342   MIA

a) Find the shortest distance between
ORD and LAX.

b) Find the shortest distance between
JFK and SFO.

c) Find the minimum spanning tree.

Answer 1

Please find the C++ program source code below. Given the small and static number of vertices and edges, the program uses the Floyd Warshall Algorithm to compute the shortest distance between vertices and uses Kruskal's Algorithm to find the minimum spanning tree. Also added comments for a clear understanding of the program and the steps involved.

C++ Program

#include<bits/stdc++.h>
#define pp pair < long long, long long >
#define MAX_D 100001
#define edge pair < int, int >

using namespace std;

int dist[10][10];
vector < pair < int, edge > > Graph, MST;
int n, e, parent[100];

void initialiseGraph() {
/* Map the cities to indexes for simplification
SFO -0
BOS -1
ORD -2
JFK -3
DFW -4
MIA -5
LAX -6
*/

// Intialise distance between cities to MAX_D initially for FloydWarshall Graph Algorithm
for (int i = 0; i <= 6; i++) {
for (int j = 0; j <= 6; j++) {
if (i == j)
dist[i][j] = 0;
else
dist[i][j] = MAX_D;
}
}

//Add edges as given in the problem and update the dist array
dist[0][1] = 2702;
dist[0][2] = 1846;
dist[2][1] = 867;
dist[2][3] = 742;
dist[3][1] = 189;
dist[0][4] = 1464;
dist[4][2] = 802;
dist[4][5] = 1123;
dist[5][3] = 1092;
dist[5][1] = 1258;
dist[0][6] = 339;
dist[6][4] = 1235;
dist[6][5] = 2342;

//Assuming its an undirected graph so for any edge u-->v there exists edge v-->u with same weight
dist[1][0] = 2702;
dist[2][0] = 1846;
dist[1][2] = 867;
dist[3][2] = 742;
dist[1][3] = 189;
dist[4][0] = 1464;
dist[2][4] = 802;
dist[5][4] = 1123;
dist[3][5] = 1092;
dist[1][5] = 1258;
dist[6][0] = 339;
dist[4][6] = 1235;
dist[5][6] = 2342;

//Initialise parent and add edges as given in the problem to Graph for finding Minimum Spanning Tree(MST)
for (int i = 0; i <= 6; i++) {
parent[i] = i;
}
MST.clear();
Graph.clear();

Graph.push_back(pair < int, edge > (2702, edge(0, 1)));
Graph.push_back(pair < int, edge > (1846, edge(0, 2)));
Graph.push_back(pair < int, edge > (867, edge(2, 1)));
Graph.push_back(pair < int, edge > (742, edge(2, 3)));
Graph.push_back(pair < int, edge > (189, edge(3, 1)));
Graph.push_back(pair < int, edge > (1464, edge(0, 4)));
Graph.push_back(pair < int, edge > (802, edge(4, 2)));
Graph.push_back(pair < int, edge > (1123, edge(4, 5)));
Graph.push_back(pair < int, edge > (1092, edge(5, 3)));
Graph.push_back(pair < int, edge > (1258, edge(5, 1)));
Graph.push_back(pair < int, edge > (339, edge(0, 6)));
Graph.push_back(pair < int, edge > (1235, edge(6, 4)));
Graph.push_back(pair < int, edge > (2342, edge(6, 5)));

Graph.push_back(pair < int, edge > (2702, edge(1, 0)));
Graph.push_back(pair < int, edge > (1846, edge(2, 0)));
Graph.push_back(pair < int, edge > (867, edge(1, 2)));
Graph.push_back(pair < int, edge > (742, edge(3, 2)));
Graph.push_back(pair < int, edge > (189, edge(1, 3)));
Graph.push_back(pair < int, edge > (1464, edge(4, 0)));
Graph.push_back(pair < int, edge > (802, edge(2, 4)));
Graph.push_back(pair < int, edge > (1123, edge(5, 4)));
Graph.push_back(pair < int, edge > (1092, edge(3, 5)));
Graph.push_back(pair < int, edge > (1258, edge(1, 5)));
Graph.push_back(pair < int, edge > (339, edge(6, 0)));
Graph.push_back(pair < int, edge > (1235, edge(4, 6)));
Graph.push_back(pair < int, edge > (2342, edge(5, 6)));
}

//This method calculates shortest distance from each vertex to every other vertex and stores in the dist array
void floydWarshall() {
for (int k = 0; k <= 6; k++) {
for (int i = 0; i <= 6; i++) {
for (int j = 0; j <= 6; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}

//Returns the parent of vertex x
int findSet(int x, int * parent) {
if (x != parent[x]) {
parent[x] = findSet(parent[x], parent);
}
return parent[x];
}

//Constructs a Minimum Spanning tree and store results in MST using Kruskal's Algorithm
void kruskal() {
sort(Graph.begin(), Graph.end());
for (int i = 0; i < Graph.size(); i++) {
int pu = findSet(Graph[i].second.first, parent);
int pv = findSet(Graph[i].second.second, parent);
if (pu != pv) {
MST.push_back(Graph[i]);
parent[pu] = parent[pv];
}
}
}

int main() {
initialiseGraph();
floydWarshall();
cout << "Distance between ORD and LAX is " << dist[2][6] << endl;
cout << "Distance between JFK and SFO is " << dist[3][0] << endl;

/*Apply Kruskal's algorithm and print the minimum spanning tree as u-->v w where u,v are vertices and w denotes the
edge weight */
kruskal();
for (int i = 0; i < MST.size(); i++)
cout << MST[i].second.first << " " << MST[i].second.second << " " << MST[i].first << endl;

}