I\'m trying to construct a program using C++ in which a user constructs a weight
ID: 3911846 • Letter: I
Question
I'm trying to construct a program using C++ in which a user constructs a weighted graph and implements Dijkstra's algorithm to find the shortest path between nodes. This is the header file. I'm missing a Graph.cpp and main.cpp. Steps to help me construct those two would be greatly appreciated!
class Graph k class List; class Vertex public: char label; int dist, index List adjList; Vertex next, sprev, *prior; Vertex(char); -Vertex() class List t public: class Node f public: Vertex datum Node mext, prev int dist; Node(Vertexs, int) t: Node* head; void destr_helper(Node*) List) -List) void add(Vertexs, int); void rem(char) bool contains(char) class PQucue Vertexxheap int tail; int parent(int); int left (int); int right(int) void swap(int, int) public: PQueue() -POueueO void upheap(int); void downheap(int) void heapify(Vertexs, int) Vertexs pop) bool enpty): Vertexs vertices PQueue* dijoueue; int order; bool directed; bool has vert(char); void destr_helper(Vertex*) void trace path(Vertexs) public: Graph(bool); -Graph) friend ostream& operatorExplanation / Answer
let us see following example which is Dijkstra's program for finding shortest path:
// C program for Dijkstra's single
// source shortest path algorithm.
// The program is for adjacency matrix
// representation of the graph.
#include <stdio.h>
#include <limits.h>
// Number of vertices
// in the graph
#define V 9
// A utility function to find the
// vertex with minimum distance
// value, from the set of vertices
// not yet included in shortest
// path tree
int minDistance(int dist[],
bool sptSet[])
{
// Initialize min value
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false &&
dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
// Function to print shortest
// path from source to j
// using parent array
void printPath(int parent[], int j)
{
// Base Case : If j is source
if (parent[j] == - 1)
return;
printPath(parent, parent[j]);
printf("%d ", j);
}
// A utility function to print
// the constructed distance
// array
int printSolution(int dist[], int n,
int parent[])
{
int src = 0;
printf("Vertex Distance Path");
for (int i = 1; i < V; i++)
{
printf(" %d -> %d %d %d ",
src, i, dist[i], src);
printPath(parent, i);
}
}
// Funtion that implements Dijkstra's
// single source shortest path
// algorithm for a graph represented
// using adjacency matrix representation
void dijkstra(int graph[V][V], int src)
{
// The output array. dist[i]
// will hold the shortest
// distance from src to i
int dist[V];
// sptSet[i] will true if vertex
// i is included / in shortest
// path tree or shortest distance
// from src to i is finalized
bool sptSet[V];
// Parent array to store
// shortest path tree
int parent[V];
// Initialize all distances as
// INFINITE and stpSet[] as false
for (int i = 0; i < V; i++)
{
parent[0] = -1;
dist[i] = INT_MAX;
sptSet[i] = false;
}
// Distance of source vertex
// from itself is always 0
dist[src] = 0;
// Find shortest path
// for all vertices
for (int count = 0; count < V - 1; count++)
{
// Pick the minimum distance
// vertex from the set of
// vertices not yet processed.
// u is always equal to src
// in first iteration.
int u = minDistance(dist, sptSet);
// Mark the picked vertex
// as processed
sptSet[u] = true;
// Update dist value of the
// adjacent vertices of the
// picked vertex.
for (int v = 0; v < V; v++)
// Update dist[v] only if is
// not in sptSet, there is
// an edge from u to v, and
// total weight of path from
// src to v through u is smaller
// than current value of
// dist[v]
if (!sptSet[v] && graph[u][v] &&
dist[u] + graph[u][v] < dist[v])
{
parent[v] = u;
dist[v] = dist[u] + graph[u][v];
}
}
// print the constructed
// distance array
printSolution(dist, V, parent);
}
// Driver Code
int main()
{
// Let us create the example
// graph discussed above
int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 0, 10, 0, 2, 0, 0},
{0, 0, 0, 14, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
dijkstra(graph, 0);
return 0;
}