Dijkstra算法的C语言程序

Dijikstra算法是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。该算法是由荷兰计算机科学家迪杰斯特拉于1959年提出的。

程序来源：Dijkstra's Algorithm。

百度百科：Dijkstra算法。

维基百科：Dijkstra's Algorithm。

C语言程序（去除了原文中非标准的C语言代码）：

#include<stdio.h>#define INFINITY 9999#define MAX 10void dijikstra(int G[MAX][MAX], int n, int startnode);int main(){    int G[MAX][MAX], i, j, n, u;    PRintf("/nEnter the no. of vertices:: ");    scanf("%d", &n);    printf("/nEnter the adjacency matrix::/n");    for(i=0;i < n;i++)        for(j=0;j < n;j++)            scanf("%d", &G[i][j]);    printf("/nEnter the starting node:: ");    scanf("%d", &u);    dijikstra(G,n,u);}void dijikstra(int G[MAX][MAX], int n, int startnode){    int cost[MAX][MAX], distance[MAX], pred[MAX];    int visited[MAX], count, mindistance, nextnode, i,j;    for(i=0;i < n;i++)        for(j=0;j < n;j++)            if(G[i][j]==0)                cost[i][j]=INFINITY;            else                cost[i][j]=G[i][j];    for(i=0;i< n;i++) {        distance[i]=cost[startnode][i];        pred[i]=startnode;        visited[i]=0;    }    distance[startnode]=0;    visited[startnode]=1;    count=1;    while(count < n-1) {        mindistance=INFINITY;        for(i=0;i < n;i++)            if(distance[i] < mindistance&&!visited[i]) {                mindistance=distance[i];                nextnode=i;            }        visited[nextnode]=1;        for(i=0;i < n;i++)            if(!visited[i])                if(mindistance+cost[nextnode][i] < distance[i]) {                    distance[i]=mindistance+cost[nextnode][i];                    pred[i]=nextnode;                }            count++;    }    for(i=0;i < n;i++)        if(i!=startnode) {            printf("/nDistance of %d = %d", i, distance[i]);            printf("/nPath = %d", i);            j=i;            do {                j=pred[j];                printf(" <-%d", j);            }            while(j!=startnode);        }    printf("/n");}程序运行结果：
Enter the no. of vertices:: 4Enter the adjacency matrix::0 1 1 11 0 1 01 1 0 11 0 1 0Enter the starting node:: 1Distance of 0 = 1Path = 0 <-1Distance of 2 = 1Path = 2 <-1Distance of 3 = 2Path = 3 <-0 <-1