Question

C语言实现最短路问题的算法

矩阵
{12 8 16 14 13 25；
11 17 15 5 4 16；
25 31 29 19 10 12；
28 24 32 12 13 12；
20 26 24 14 5 7；
32 28 36 16 17 8}用C语言编写程序求解最短路

Answer 1

＃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);
}
}
}

追问

运行程序输入矩阵就可以计算了吗？

追答

对的

追问

两次输入的分别是什么？第一次node number输入一行，后面出现cost status然后后输入后面五行好像不对