dijkstra.cpp

用C语言实现dijkstra算法

#include "limits.h"                     /* INT_MAX等 */
#include "stdio.h"                      /* EOF(=^Z或F6),NULL */
#include "stdlib.h"
#include "string.h"

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status;                   /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
#define MAX_NAME 5                    /* 顶点字符串的最大长度+1 */
#define MAX_INFO 20                   /* 相关信息字符串的最大长度+1 */
typedef int VRType;
typedef char InfoType;
typedef char VertexType[MAX_NAME];
#define INFINITY INT_MAX                  /* 用整型最大值代替∞ */
#define MAX_VERTEX_NUM 20                 /* 最大顶点个数 */

typedef enum{DG, DN, AG, AN}GraphKind;    /* {有向图,有向网,无向图,无向网} */
typedef struct
{
VRType adj;                             /* 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； */
                                            /* 对带权图，c则为权值类型 */
InfoType *info;                         /* 该弧相关信息的指针(可无) */
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
VertexType vexs[MAX_VERTEX_NUM];        /* 顶点向量 */
AdjMatrix arcs;                         /* 邻接矩阵 */
int vexnum, arcnum;                     /* 图的当前顶点数和弧数 */
GraphKind kind;                         /* 图的种类标志 */
}MGraph;

typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int ShortPathTable[MAX_VERTEX_NUM];

int LocateVex(MGraph G, VertexType u)
{
int i;

for (i = 0; i < G.vexnum; i++)
{
   if (strcmp(u, G.vexs[i]) == 0)
   {
    return i;
   }
}
return -1;
}

Status CreateDN(MGraph *G)
{
int i, j, k, w, IncInfo;
char s[MAX_INFO], *info;
VertexType va, vb;

printf("请输入有向图G的顶点数,弧数,弧是否含有其它信息(是:1,否:0):");
scanf("%d,%d,%d",&(*G).vexnum, &(*G).arcnum, &IncInfo);
printf("请输入%d个顶点的值(<%d个字符):\n", (*G).vexnum, MAX_NAME);
for (i = 0; i < (*G).vexnum; i++)
{
   scanf("%s", (*G).vexs[i]);
}
//初始化
for (i = 0; i < (*G).vexnum; i++) 
{
   for (j = 0; j < (*G).vexnum; j++)
   {
    (*G).arcs[i][j].adj = INFINITY;
    (*G).arcs[i][j].info = NULL;
   }
}
printf("请输入%d条弧的弧尾 弧头 权值(以空格作为间隔):\n", (*G).arcnum);
for (k = 0; k < (*G).arcnum; k++)
{
   scanf("%s%s%d%*c", va, vb, &w);
   i = LocateVex(*G, va);
   j = LocateVex(*G, vb);
   (*G).arcs[i][j].adj = w;
   if (IncInfo)
   {
    printf("请输入该弧的相关信息(<%d个字符): ", MAX_INFO);
    gets(s);
    w = strlen(s);
    if (w)
    {
     info = (char *) malloc ((w + 1) * sizeof(char));
     strcpy(info, s);
     (*G).arcs[i][j].info = info;
    }
   }
}
(*G).kind = DN;
return OK;
}

void dijkstra(MGraph G, int v0, PathMatrix *p, ShortPathTable *D)  //dijkstra算法实现
{
int v, w, i, j, min;
Status final[MAX_VERTEX_NUM];

for (v = 0; v < G.vexnum; v++)
{
   final[v] = FALSE;                 
   (*D)[v] = G.arcs[v0][v].adj;
   for (w = 0; w < G.vexnum; w++)   
   {
    (*p)[v][w] = FALSE;
   }
   if ((*D)[v] < INFINITY)
   {
    (*p)[v][v0] = TRUE;
    (*p)[v][v] = TRUE;
   }
} 

(*D)[v0] = 0;
final[v0] = TRUE;
for (i = 1; i < G.vexnum; i++)
{
   min = INFINITY;
   for (w = 0; w < G.vexnum; w++)
   {
    if (!final[w])
    {
     if ((*D)[w] < min)
     {
      v = w;
      min = (*D)[w];
     }
    }
   }
   final[v] = TRUE;
   for (w = 0; w < G.vexnum; w++)
   {
    if (!final[w] && min < INFINITY && G.arcs[v][w].adj
     < INFINITY && (min + G.arcs[v][w].adj < (*D)[w]))
    {
     (*D)[w] = min + G.arcs[v][w].adj;
     for (j = 0; j < G.vexnum; j++)
     {
      (*p)[w][j] = (*p)[v][j]; 
     }
     (*p)[w][w] = TRUE;
    }
   }
}
}

int main()
{
int i, j, v0 = 0;
MGraph g;
PathMatrix p;
ShortPathTable d;

CreateDN(&g);
dijkstra(g, v0, &p, &d);
printf("最短路径数组p[i][j]如下:\n");
for (i = 0; i < g.vexnum; i++)
{
   for (j = 0; j < g.vexnum; j++)
   {
    printf("%2d", p[i][j]);
   }
   printf("\n");
}
printf("%s到各顶点的最短路径为：\n",g.vexs[0]);

for (i = 1; i < g.vexnum; i++)
{
	printf("[%s到%s]: ",g.vexs[0],g.vexs[i]);
	printf("%s",g.vexs[0]);
   for (j = 1; j < g.vexnum; j++)
   {
	   if(p[i][j]>0)
		printf("->%s", g.vexs[j]);
   }
   printf(":%d\n",d[i]);
}

return 0;
}