Question

用dijkstra算法解决最短路径问题c语言代码实现时怎样将每一个路径的顶点次序依次输出出来？

Answer 1

dijkstra算法原理主要就是已知源节点（v）和n个节点间代价函数（有向网络矩阵cost），通过不断将节点加入到一个节点子集S中，使得经过加入S后的各节点的路径代价是最小的，直至S节点包含了所有的n个节点停止。（具体算法阐明网上很多资料）。闲话少说，直接附程序吧～
/*
readme:
first,you need to input the node number, the cost matrix and the source node;
then the program will compute the best path.
finally,the program will output the lowest distance to the destination node, the pre-node and show the best path.
*/
＃i nclude<stdio.h>
＃i nclude <stdlib.h>
//Dijkstra算法实现函数
void Dijkstra(int n,int v,int dist[],int prev[],int **cost)
{
int i;
int j;
int maxint = 65535;//定义一个最大的数值，作为不相连的两个节点的代价权值
int *s ;//定义具有最短路径的节点子集s
s = (int *)malloc(sizeof(int) * n);
//初始化最小路径代价和前一跳节点值
for (i = 1; i <= n; i++)
{
dist[i] = cost[v][i];
s[i] = 0;
if (dist[i] == maxint)
{
prev[i] = 0;
}
else
{
prev[i] = v;
}
}
dist[v] = 0;
s[v] = 1;//源节点作为最初的s子集
for (i = 1; i < n; i++)
{
int temp = maxint;
int u = v;
//加入具有最小代价的邻居节点到s子集
for (j = 1; j <= n; j++)
{
if ((!s[j]) && (dist[j] < temp))
{
u = j;
temp = dist[j];
}
}
s[u] = 1;
//计算加入新的节点后，更新路径使得其产生代价最短
for (j = 1; j <= n; j++)
{
if ((!s[j]) && (cost[u][j] < maxint))
{
int newdist = dist[u] + cost[u][j];
if (newdist < dist[j])
{
dist[j] = newdist;
prev[j] = u;
}
}
}
}
}
//展示最佳路径函数
void ShowPath(int n,int v,int u,int *dist,int *prev)
{
int j = 0;
int w = u;
int count = 0;
int *way ;
way=(int *)malloc(sizeof(int)*(n+1));
//回溯路径
while (w != v)
{
count++;
way[count] = prev[w];
w = prev[w];
}
//输出路径
printf("the best path is:\n");
for (j = count; j >= 1; j--)
{
printf("%d -> ",way[j]);
}
printf("%d\n",u);
}
//主函数，主要做输入输出工作
void main()
{
int i,j,t;
int n,v,u;

int **cost;//代价矩阵
int *dist;//最短路径代价
int *prev;//前一跳节点空间
printf("please input the node number: ");
scanf("%d",&n);
printf("please input the cost status:\n");

cost=(int **)malloc(sizeof(int)*(n+1));
for (i = 1; i <= n; i++)
{
cost[i]=(int *)malloc(sizeof(int)*(n+1));
}
//输入代价矩阵
for (j = 1; j <= n; j++)
{
for (t = 1; t <= n; t++)
{
scanf("%d",&cost[j][t]);
}
}

dist = (int *)malloc(sizeof(int)*n);
prev = (int *)malloc(sizeof(int)*n);
printf("please input the source node: ");
scanf("%d",&v);
//调用dijkstra算法
Dijkstra(n, v, dist, prev, cost);
printf("*****************************\n");
printf("have confirm the best path\n");
printf("*****************************\n");
for(i = 1; i <= n ; i++)
{
if(i!=v)
{
printf("the distance cost from node %d to node %d is %d\n",v,i,dist[i]);
printf("the pre-node of node %d is node %d \n",i,prev[i]);
ShowPath(n,v,i, dist, prev);
}
}
}