Develop a program that reads the numbers of two nodes of a weighted graph and outputs the shortest path between the 2 nodes. in C++

Question

Develop a program that reads the numbers of two nodes of a weighted graph and outputs the shortest path between the 2 nodes. In C++

Summary

A graph is defined as a collection of vertices and directed edges. After that, two nodes are selected from the user, and the shortest distance between them is calculated and printed to the console.

Explanation

The source and destination nodes are used as input. Then, using a modified version of the Depth First Search, all the basic pathways are traversed from source to destination. The source and destination, as well as the graph, are supplied to a function called leastCost, and a recursion method is performed. The least-cost between the graph’s source and destination vertices is returned by this function. A graph is initialized with a set of vertices and edges in the main method. The leastCost function is then invoked to determine the shortest path cost and output it to the console.

Code

#include <bits/stdc++.h>
using namespace std;
int path[20]; int cc=0;
int leastCost(bool visit[], int graphs[][5], int s, int d,int m)
{
    if (s == d)
        return 0;
    visit[s] = 1;
    int result=99999999;
    for (int i = 0; i < m; i++) {
        if (graphs[s][i] !=99999999 && !visit[i]) {
            int current = leastCost(visit, graphs,i,d,m);
            if (current < 99999999) {
                if(result>(graphs[s][i]+current)){
                path[cc]=i; cc++;
                result=graphs[s][i]+current;
                }
            }
        }
    }
    visit[s] = 0;
    return result;
}
int main()
{
    int graphs[5][5];
    for (int i = 0; i < 5;i++) {
        for (int j = 0;j < 5;j++) {
            graphs[i][j] = 99999999;
        }
    }
    bool visit[5] = { 0 };
    graphs[0][1]=-7;
    graphs[0][3]=-2;
    graphs[1][2]=-11;
    graphs[3][3]=-3;
    graphs[3][4]=-4;
    int p = 0;
    int r = 4;
    visit[p] = 1;
    path[0]=p;
    cc++;
    cout<<"least cost = "<<leastCost(visit, graphs,p,r,5)<<endl;
    cout<<"Shorest path:"<<endl;
    cout<<path[0];
    for(int i=cc-1;i>0;i--)
    cout<<" -> "<<path[i];
    return 0;
}

Output

Also, read the Given below-defined UML class diagram.