Please help C++. Write a program that will display the minimum path between any two vertices in a given graph. The program will input the graph from a file provided by the user. It will prompt the user for entering the name of the start vertex and the end vertex. It will find the minimum path between the two vertices. It will display the minimum path showing all the vertices along the path. It will also display the total distance along the minimum path.

How do you make the vertices graph? How do you pass it to DIjkstra's function? Just complete the code to get the output right. Use dijkstra's implentation below. Can you explain the things needed to create a graph representation of the nodes?

class graph{

private:

int NUMNODES = 100

int distance;

int path;

string string_input[20];

public:

void dijkstra(graph* graph1, int* distance1, int* source1);

int min_path();

};

Data Set 1

Test the program for the data set 1 listed. Enter this data into a file and input the data from the file.

The data consists of two parts. In the first part, each line represents a vertex. It contain two values. The first value specifies the vertex number. The second value specifies the vertex name. The first part ends when a line contains -1 by itself. In the second part, each line represents an edge. It contains three values. The first two values specify two vertices connecting the edge. The third value specifies the weight of the edge. This part ends when a line contains -1 by itself.

0 SF

1 LA

2 CHICAGO

3 NY

4 PARIS

5 LONDON

-1

0 1 80

0 2 200

0 3 300

1 2 230

1 5 700

2 3 180

3 4 630

3 5 500

4 5 140

-1

Data Set 1: Test Run 1

Run the program using SF as the start vertex. Program input/output dialog is shown below. The user input is shown in bold.

Enter Start Vertex: SF

Enter End Vertex :LONDON

Min Path: SF LA LONDON 780

Data Set 1: Test Run 2

Enter Start Vertex: SF

Enter End Vertex : PARIS

Min Path: SF LA LONDON PARIS 920

The implementation for Dijkstras algorithm using the priority queue.

class DijkElem {

public:

int vertex, distance;

DijkElem() { vertex = -1; distance = -1; }

DijkElem(int v, int d) { vertex = v; distance = d; }

};

// Dijkstras shortest paths algorithm with priority queue

void Dijkstra(Graph* Graph1, int* distance1, int source1) {

int i, currentVertex, weight; // v is current vertex DijkElem temp;

DijkElem E[Graph1->e()]; // Heap array with lots of space

temp.distance = 0;

temp.vertex = source1;

E[0] = temp; // Initialize heap array heap

H(E, 1, Graph1->e()); // Create heap

for (i=0; in(); i++) { // Now, get distances

do {

if (H.size() == 0) return; // Nothing to remove

temp = H.removefirst();

currentVertex = temp.vertex;

}

while (Graph1->getMark(currentVertex) == VISITED);

Graph1->setMark(currentVertex, VISITED);

if (distance1[v] == INFINITY) return; // Unreachable vertices

for (weight=G->first(v); wn();

w = Graph1->next(v,w))

if (distance1[weight] > (distance1[currentVertex] + Graph1->weight(v, w))) {

// Update D

distance1[weight] = distance[currentVertex] + Graph1->weight(v, w);

temp.distance = distance1[weight];

temp.vertex = weight;

H.insert(temp); // Insert new distance in heap

} } }