用Dijkstra算法求最短路径

Question

问题描述：交通网络中常常会提出这样的问题：两地之间是否有路相通？在有多条通路的情况下，哪一条最短？以上问题就是带权图中求最短路径的问题。
基本要求：
一 用DIJKSTRA算法求最短路径，图中的顶点数N 不得少于10个，待输入的数据（边的关联顶点信息和权值）存储在预先立的文件中。
二 用户输入源点和目标点后，程序应输出源点到目标点的最短路径，并计算出途中所需时间或花费的交通费用。
最好以河北省具体的地图为准，参数最好要真实！
在线等！～ Q471347130 phone15081474660沧州

Answer 1

#include <stdio.h>
#include <string.h>
#define MAX 20
int mincost(int V[], int D[], int n);
int main()
{
int C[MAX][MAX];
int D[MAX], V[MAX] = { 0 }; /*数组V用来表示每次计算加入集合V的点，1为加入了，0为还没有加入*/
int n, i, j, k, w, sum;
printf("请输入顶点个数:");
scanf("%d", &n);
printf("\n请输入建立后的临接矩阵(用n*n矩阵表示), 输入100000表示无穷大:\n");
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
scanf("%d", &C[i][j]);
}
}
V[1] = 1; /*1为源点*/
for(i = 1; i <= n; i++)
{
D[i] = C[1][i]; /*D置初值*/
}
for(i = 1; i <= n; i++)
{
/*从集合S(即没有经过计算的点）中选出一个点w（即V中值为0），使D[w]值最小*/
w = mincost(V, D, n);
V[w] = 1;
/*由于w的选定，S中的每个点(即V中值为0的点都要重新计算其到源点的最小值*/
for(k = 2; k <= n; k++)
{
if(V[k] == 0)
{
sum = D[w] + C[w][k];
if(sum < D[k])
{
D[k] = sum;
}
}
}
}
for(i = 2; i <= n; i++)
{
printf("D[%d] = %d\n", i, D[i]);
}
memset(V, 0, MAX * sizeof(int)); /*初始化*/
return 0;
}

int mincost(int V[], int D[], int n)
{
int temp = 10000000, i, w = 2;
for(i = 2;i <= n; i++)
{
if(V[i] == 0 && D[i] < temp)
{
temp = D[i];
w = i;
}
}
return w;
}

改成文件的就行了