Dijkastra.cpp

#include <iostream>
using namespace std;
int n,i,j,s[100],p[100],path[100];
struct Graph
{
    int n,e,c;
    int a[101][101];
};
Graph g;
void Dijkastra(int x)
{
    int c, mini, y,ex,ey;
    int const MAX=5000;
    cout<<"number of nodes=";
    cin>>g.n;
    cout<<"number of edges=";
    cin>>g.e;
    for(i=1; i<=g.n; i++)
        for(j=1; j<=g.n; j++)
            if(i==j)
                g.a[i][j]=0;
            else g.a[i][j]=MAX;
    for(int k=1; k<=g.e; k++)
    {
        cout<<"the nodes adjacent to the edge "<<g.e<<"are: ";
        cin>>ex>>ey;
        cout<<"the cost of the edge: ";
        cin>>g.c;
        g.a[ex][ey]=g.c;
    }
    s[x]=1;
    for(i=1; i<=g.n; i++)
    {
        path[i]=g.a[x][i];
        if(i!=x && path[i]<MAX)
            p[i]=x;
    }
    for(i=1; i<=g.n-1; i++)
    {
        for(j=1, mini=MAX; j<=g.n; j++)
            if(s[j]==0 && path[j]<mini)
            {
                mini=path[j];
                y=j;
            }
        s[y]=1;
        for(j=1; j<=g.n; j++)
            if(s[j]==0 && path[j]>path[y]+g.a[y][j])
            {
                path[j]=path[y]+g.a[y][j];
                p[j]=y;
            }
    }
}
void path_graph(int i)
{
    if(p[i]!=0)
        path_graph(p[i]);
    cout<<i<<" ";
}

int main()
{
    int x;
    cout<<"x=";
    cin>>x;
    Dijkastra(x);
    for(i=1; i<=g.n; i++)
        if(i!=x)
            if(p[i]!=0)
            {
                cout<<"the path with the lowest cost from node "<<x;
                cout<<" to "<<i<<" has the cost "<<path[i]<<endl;
                path_graph(i);
                cout<<endl;
            }
            else
                cout<<"there is not a path between "<<x<<" and "<<i<<endl;
    return 0;
}