动态问题求最短路径c语言程序,Dijkstra算法求最短路径问题完整C代码

/* Dijkstra算法求图的最短路径问题C代码 */

#include

#include

#include

#define MaxSize 20

#define INFINITY 65535

typedef char VertexType;

//定义图 的邻接矩阵表示法结构

typedef struct Graph {

VertexType ver[MaxSize&＃43;1];

int edg[MaxSize][MaxSize];

}Graph;

//邻接矩阵法图的生成函数

void CreateGraph( Graph *g )

{

int i &＃61; 0;

int j &＃61; 0;

int VertexNum;

VertexType Ver;

printf("请输入图的顶点:\n");

while( &＃39;\n&＃39; !&＃61; (Ver&＃61;getchar()) )

g->ver[i&＃43;&＃43;] &＃61; Ver;

g->ver[i] &＃61; &＃39;\0&＃39;;

VertexNum &＃61; strlen(g->ver);

printf("请输入相应的的邻接矩阵:\n");

for( i&＃61;0; i

for( j&＃61;0; j

scanf("%d", &g->edg[i][j]);

}

//打印图的结点标识符和邻接矩阵

void PrintGraph( Graph g )

{

int i, j;

int VertexNum &＃61; strlen(g.ver);

printf("图的顶点为:\n");

for( i&＃61;0; i

printf("%c ", g.ver[i]);

printf("\n");

printf("图的邻接矩阵为:\n");

for( i&＃61;0; i

for( j&＃61;0; j

printf("%d ", g.edg[i][j]);

printf("\n");

}

}

//求图的顶点数

int CalVerNum( Graph g )

{

return strlen(g.ver);

}

//将不邻接的顶点之间的权值设置为INFINITY

void SetWeight( Graph *g )

{

for( int i&＃61;0; i

for( int j&＃61;0; j

if( 0 &＃61;&＃61; g->edg[i][j] )

g->edg[i][j] &＃61; INFINITY;

}

//Dijkstra求最短路径函数

void Dijkstra( Graph g )

{

int VertexNum &＃61; CalVerNum( g );

int j;

int mini;

int index &＃61; 0;

int *used &＃61; (int *)malloc(sizeof(int)*VertexNum);

int *distance &＃61; (int *)malloc(sizeof(int)*VertexNum);

int *parent &＃61; (int *)malloc(sizeof(int)*VertexNum);

int *last &＃61; (int *)malloc(sizeof(int)*VertexNum);

SetWeight( &g );//设置权值

for( int i&＃61;0; i

used[i] &＃61; 0;

distance[i] &＃61; g.edg[0][i]; //初始化为与编号为0的顶点的距离

last[i] &＃61; 0;

}

used[0] &＃61; 1;

parent[index&＃43;&＃43;] &＃61; 0;

for( i&＃61;0; i

j &＃61; 0;

mini &＃61; INFINITY;

for( int k&＃61;0; k

if( (0 &＃61;&＃61; used[k]) && (distance[k]

mini &＃61; distance[k];

j &＃61; k;//j为刚刚找到的V-U中到源点路径最短的顶点

}

used[j] &＃61; 1;

for( k&＃61;0; k

if( (0 &＃61;&＃61; used[k]) && (distance[k] > distance[j] &＃43; g.edg[j][k]) ) { //由于有顶点新加入U集合&＃xff0c;对距离数组distance进行更新&＃xff0c;比较原路径长度与以新加入的顶点为中间点的路径长度

distance[k] &＃61; distance[j] &＃43; g.edg[j][k];

}

parent[index&＃43;&＃43;] &＃61; j;

}

printf("%c到%c的最短路径经过顶点依次为:\n", g.ver[0], g.ver[VertexNum-1]);

for( i&＃61;0; i

printf("%c ", g.ver[parent[i]]);

printf("\n");

printf("最短路径长度为: %d\n", mini);

}

int main()

{

Graph g;

CreateGraph( &g );

PrintGraph( g );

Dijkstra( g );

return 0;

}

测试数据及结果