本程序以下面的图为例，求v0到其他各个顶点的最短距离。

运行结果：

本程序在运行时必须在其同目录中包含in.txt文件。

in.txt文件内容的说明：第一行为顶点个数，边数，以后各行是边及其权值。本例为：第一行 6 -- 六个顶点，8 -- 八条边，第二行 0 2 10，v0到v2有条权值为10的边，下面是以上面的图为例的in.txt的内容：

6 8
0 2 10
0 5 100
0 4 30
1 2 5
2 3 50
3 5 10
4 3 20
4 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);
 }
}

评论