sample file

readme.md

source file

main.cpp

#include<stdlib.h>
#include<stdio.h>
#define x 9999
#define max 9999
int data[10][10];
// record the value of the shortest path from the start
int dist[10];
// record the shortest path from the start
int path[10];
int kmin(int,int);
// compute the value of the shortest path
void fpath(int a[][10]);
// compute the shortest path
int froute(int a[][10]);
int main()
{
    int i,m;
    // adjacency matrix
    // upper triangular matrix
    int a[10][10]={
        {x,4,2,3,x,x,x,x,x,x},
        {x,x,x,x,10,9,x,x,x,x},
        {x,x,x,x,6,7,10,x,x,x},
        {x,x,x,x,x,3,8,x,x,x},
        {x,x,x,x,x,x,x,4,8,x},
        {x,x,x,x,x,x,x,9,6,x},
        {x,x,x,x,x,x,x,5,4,x},
        {x,x,x,x,x,x,x,x,x,8},
        {x,x,x,x,x,x,x,x,x,4},
        {x,x,x,x,x,x,x,x,x,x} };

    
    fpath(a);
    printf(" the value of the shortest path is %d\n",dist[9]);
    m=froute(a);
    for(i=m-1;i>=0;i--)
        printf("the shortest path is %d\n",path[i]);
    return 0;
}
// compute the value of the shortest path
void fpath(int a[][10])
{
    int i,j,k;
    dist[0]=0;
    // the current node is i
    // from the second node
    for(i=1;i<10;i++)
    {
        k=max;
        // i=1,j=0...1 a[0][1]
        // i=2,j=0...2 a[0][2],a[1][2]
        // the predecessor node is j
        for(j=0;j<i;j++)
        {
            if(a[j][i]!=x)
            {
                if((dist[j]+a[j][i])<k)
                    k=dist[j]+a[j][i];        
            }

        }
        dist[i]=k;
    }
}
//  compute the shortest path
int froute(int a[][10])
{
    int j,b,k=1,i=9;
    // the final node
    path[0]=10;
    while(i>0)
    {
        for(j=i-1;j>=0;j--)
        {
            if(a[j][i]!=x)
            {
                b=dist[i]-a[j][i];
                if(b==dist[j])
                {
                    path[k++]=j+1;
                    i=j;
                    break;
                }
            }
        }
    }
    return k;
}