本程序以下面的图为例，求v0到其他各个顶点的最短距离。 运行结果：   本程序在运行时必须在其同目录中包含in.txt文件。 in.txt文件内容的说明：第一行为顶点个数，边数，以后各行是边及其权值。本例为：第一行 6 -- 六个顶点，8 -- 八条边，第二行 0 2 10，v0到v2有条权值为10的边，下面是以上面的图为例的in.txt的内容： 6 80 2 100 5 1000 4 301 2 52 3 503 5 104 3 204 5 60 以下是主程序： #include "stdio.h"#include "stdlib.h"#define INT_MAX 32767#define INFINITY INT_MAX //最大值#define MAX_VERTEX_NUM 20 //最大顶点个数#define TRUE 1#define FALSE 0 typedef struct ArcCell{ int adj;}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct{ int vex[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum, arcnum;}MGraph; void printPath(int*, int);    //打印一条路径void output(MGraph*, int, int*, int*); //最后输出void CreateMGraph(MGraph*);    //从文件（in.txt）中读取数据，创建图的邻接矩阵void ShortestPath_DIJ(MGraph*, int, int*, int*); //最短路径算法 -- DijKstra算法 int main(){ int P[MAX_VERTEX_NUM]; //路径向量 int D[MAX_VERTEX_NUM]; //路径权值向量 int v0 = 0; //起始点 MGraph G;  CreateMGraph(&G); ShortestPath_DIJ(&G, v0, P, D); output(&G, v0, P, D);  return 0;} void CreateMGraph(MGraph *GPtr){ int i = 0; int j = 0; int v1 = 0, v2 = 0, weight = INFINITY; FILE* in = NULL; if((in=fopen("in.txt", "r")) == NULL){  printf("Graph file could not be opened! "   "Please check there is in.txt in current directory.\n");  exit(0); } fscanf(in, "%d %d", &GPtr->vexnum, &GPtr->arcnum); printf("vexnum = %d, arcnum = %d\n\n", GPtr->vexnum, GPtr->arcnum);  for(i=0; i<GPtr->vexnum; i++)   //初始化边的权值为无穷大  for(j=0; j<GPtr->vexnum; j++)   GPtr->arcs[i][j].adj = INFINITY;  for(i=0; i<GPtr->arcnum; i++){   //从文件中读取边及权值  fscanf(in, "%d %d %d", &v1, &v2, &weight);  GPtr->arcs[v1][v2].adj = weight;   }  fclose(in); printf("\tv0\tv1\tv2\tv3\tv4\tv5\n");  for (i=0; i<GPtr->vexnum; i++){   //打印图的邻接矩阵  printf("v%d\t", i);  for (j=0; j<GPtr->vexnum; j++){   if(GPtr->arcs[i][j].adj == INFINITY)    printf("∞\t");   else    printf("%d\t", GPtr->arcs[i][j].adj);  }  printf("\n"); }} void ShortestPath_DIJ(MGraph *GPtr, int v0, int *P, int *D){ int i, v, w; int min = INFINITY; int groupS[MAX_VERTEX_NUM];  for(i=0; i<GPtr->vexnum; i++){  D[i] = GPtr->arcs[v0][i].adj;  if(D[i] < INFINITY) P[i]=v0;      else P[i]=-1;  groupS[i] = FALSE; }  groupS[v0] = TRUE; D[v0] = 0;  for (i=1; i<GPtr->vexnum; i++){  min = INFINITY;  for(w=0; w<GPtr->vexnum; w++){   if(!groupS[w])    if(D[w] < min){     v = w;     min = D[w];    }  }   groupS[v] = TRUE;   for(w=0; w<GPtr->vexnum; w++)   if (!groupS[w] && (min + GPtr->arcs[v][w].adj < D[w])){    D[w] = min + GPtr->arcs[v][w].adj;    P[w] = v;   } } } void output(MGraph* GPtr, int v0, int *P, int *D){ int i; printf("\n\nPATH\t\t\t\tLENGTH\n\n"); for(i=0; i<GPtr->vexnum; i++)  if (i != v0 && D[i] < INFINITY) {   printPath(P, i);   printf("\b\b\b\t\t\t%-4d", D[i]);   printf("\n");  }} void printPath(int *P, int i){ if (P[i] == -1){  printf("v%d -> ", i);  return; } else{  printPath(P, P[i]);  printf("v%d -> ", i); }}

评论