Hi, I need help with a C++ program that finds the shortest path between graphs o

Question

Hi, I need help with a C++ program that finds the shortest path between graphs or in this case cities using this text 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

Explanation / Answer

#include <stdio.h>

#include <limits.h>

// Number of vertices in the graph

#define V 5

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;

}

// A utility function to print the constructed distance array

int printSolution(int dist[], int n)

{

   printf("Vertex   Distance from Source ");

   for (int i = 0; i < V; i++)

      printf("%d tt %d ", i, dist[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)

{

     int dist[V];     // The output array. dist[i] will hold the shortest

                      // distance from src to i

     bool sptSet[V]; // sptSet[i] will true if vertex i is included in shortest

                     // path tree or shortest distance from src to i is finalized

     // Initialize all distances as INFINITE and stpSet[] as false

     for (int i = 0; i < V; i++)

        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] != INT_MAX

                                       && dist[u]+graph[u][v] < dist[v])

            dist[v] = dist[u] + graph[u][v];

     }

     // print the constructed distance array

     printSolution(dist, V);

}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.