graph.c

采用邻接矩阵实现有向网的存储

#include <stdio.h>
#include <stdlib.h>
#define INFINITY  10000

int  mincost (int  number, int D[number], int S[number] )
{
    int i,  temp;
    temp = INFINITY ;
    int w = 2 ;
    for ( i=2 ; i<=number ; i++ )
        if ( !S[i] && D[i]<temp)
        {
            temp = D[i] ;
            w = i ;
        }
    return  w ;
}
void  Dijkstra(int number,int C[number][number],int D[number+1] )
{
    int  S[number+1];
    int i ,sum,v,w;
    for ( i=1 ; i<=number; i++ )
    {
        D[i]=C[1][i] ;
        S[i]=0 ;
    }
    S [1]= 1 ;
    for ( i=1; i<number; i++)
    {
        w=mincost (number, D, S ) ;
        S[w]=1 ;
        for ( v=2 ; v<= number; v++ )
            if ( S[v]!=1 )
            {
                sum=D[w] + C[w][v] ;
                if (sum < D[v] )   D[v] = sum ;
            }
    }
}


int main()
{

    int number;
    printf("**********************\n");
    printf("   The shortest path  \n");
    printf("**********************\n");
    printf("请输入顶点个数:");
    scanf ( "%d" ,&number );
    int C[number][number];
    int D[number+1];
    int i,j,w;
    for (i = 1; i <= number; ++i)
    {
        for (j = 1; j <= number; ++j)
        {
            if(i!=j)
            {
                printf("%d到%d的路径长:",i,j);
                scanf ("%d",&w);
            }


            if ( w == -1 )
                C[i][j] = INFINITY;
            else
                C[i][j] = w;
        }
    }
    Dijkstra(number,C,D);
     printf("**********************\n");
    for (i = 2;i <= number;i++)
    {
        if(D[i]==INFINITY)
        printf("1到%d的最短路径长为:∞\n",i);
        else
        printf("1到%d的最短路径长为:%d\n",i,D[i]);

    }
    return 0;
}