求最短通路的算法 Dijkstra算法

coolflyr_reg

我们上离散数学的时候，老师让用编程实现的一个题

[PHP]
#include <stdio.h>
#include <conio.h>

#define VertexNum 14      /*  节点数  */
#define X 10000      /*  最大值  */
enum bool {false,true};

int path[VertexNum],Vertex;   
int Graph[VertexNum][VertexNum] =      /*  图  */
/*  a  b  c  d  e  f  g  h  i  j  k  l  m  z */
{   X, 2, 2, 4, 1, X, X, X, X, X, X, X, X, X, /*a */
        2, X, 1, X, X, 4, 5, X, X, X, X, X, X, X, /*b*/
        2, 1, X, 3, X, X, 3, 5, X, X, X, X, X, X, /*c*/
        4, X, 3, X, 2, X, X, 6, 2, X, X, X, X, X, /*d*/
        1, X, X, 2, X, X, X, X, 5, X, X, X, X, X, /*e*/
        X, 4, X, X, X, X, 4, X, X, 6, X, X, X, X, /*f*/
        X, 5, 3, X, X, 4, X, 4, X, X, 7, X, X, X, /*g*/
        X, X, 5, 6, X, X, 4, X, 1, X, 2, 8, 4, X, /*h*/
        X, X, X, 2, 5, X, X, 1, X, X, X, X, 5, X, /*i*/
        X, X, X, X, X, 6, X, X, X, X, 1, X, X, 1, /*j*/
        X, X, X, X, X, X, 7, 2, X, 1, X, 2, X, 4, /*k*/
        X, X, X, X, X, X, X, 8, X, X, 2, X, 6, 3, /*l*/
        X, X, X, X, X, X, X, 4, 5, X, X, 6, X, 6, /*m*/
        X, X, X, X, X, X, X, X, X, 1, 4, 3, 6, X  /*z*/
};

int minnum(int a,int b){
        int min;
        min=(a>b)?b:a;
        return min;
}

void Dijkstra()
{
        /* Add code in here */
        int D[VertexNum],v0,v,min,i,j,count;
        int Gather[VertexNum];    /*  声明一个集合  */
        for (i=0;i<VertexNum;++i){
                Gather=false;
                D=10000;
        }
        for(j=0;j<VertexNum;++j)
                D[j]=Graph[0][j];
    printf("   ");
        for(count=0;count<VertexNum-1;count++) {
                if (count==VertexNum-2) count='z'-'b';
                printf("%3c",'b'+count);
        }
        printf("\n");
        Vertex=v0=0;
    Gather[v0]=true;
        for(j=1;j<VertexNum;++j) {
                min=10000;
                for (v=0;v<VertexNum;++v){
                        if(Gather[v]) printf("   ");
                        if(!Gather[v]){
                                D[v]=minnum(D[v],D[Vertex]+Graph[Vertex][v]);
                                if(D[v]==10000) printf("%3c",'*'); else printf("%3d",D[v]);
                                if(min>D[v]){
                                        min=D[v];
                                        v0=v;
                                }
                        }
                }
                Gather[v0]=true;
                Vertex=v0;
        for(v=1; v<VertexNum; v++) {
                if (!Gather[v] && D[Vertex] + Graph[Vertex][v] <D[v]) {
                        D[v] = D[Vertex] + Graph[Vertex][v];
                        path[v] = Vertex;
                }
        }
                printf("\n");
        }
        printf("The minimum value is %d\n",D[VertexNum-1]);
}

void main()
{
        int k;
        clrscr();
        Dijkstra();
        printf("The path is: ");
        k = VertexNum-1;
        do {                      /*  输出路径  */
                printf("%c<--",'a'+((k==13)?'z'-'a':k));
                k  = path[k];
        } while (k!=0);
        printf("a \n");
}
[/PHP]