dijstra.c

Dijstra算法,用C语言实现.求网络最短路

#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[i]=false; 
        D[i]=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"); 
}