两点之间最短距离：贪心算法 （DIJKSTRA算法）

两点之间最短距离：贪心算法 （DIJKSTRA算法）

在交通网络日益发达的今天，针对人们关心的各种问题，利用计算机建立一
个A城市的交通咨询系统。在系统中采用图来构造各个城市之间的联系，图中
顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的耗费。
这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得
从A城到B城途中中转次数最少；如何选择一条路径使得从A城到B城里程最
短；如何选择一条路径使得从A城到B城花费最低等等的一系列问题。

#include
#define max1 1000
int a[10][10];
int dist[10];
int path[10];
int set[10];
int min;
int v;
void fun(int n)
{

if(n==0)
{
	printf("A");
}
else{
	fun(path[n]);
	printf("->%c",n+'A');
}

}
int main()
{
for(int i=0;i<=5;i++)
{
for(int j=0;j<=5;j++)
{
a[i][j]=max1;
}
}
a[0][1]=10;
a[0][3]=30;
a[0][4]=100;
a[1][2]=50;
a[2][4]=10;
a[3][2]=20;
a[3][4]=60;
dist[0]=0;
path[0]=-1;
set[0]=1;
for(int i=1;i<=4;i++)
{
if(a[0][i]>0)
{
path[i]=0;
dist[i]=a[0][i];
}
else
{
path[i]=-1;
dist[i]=max1;
}
}
for(int k=1;k<=4;k++)
{
printf("%d “,dist[k]);
}
printf(”n");
for(int k=1;k<=4;k++)
{
printf("%d “,path[k]);
}
printf(”n");
for(int k=1;k<=4;k++)
{
printf("%d “,set[k]);
}
printf(”n");
for(int i=1;i<=4;++i)
{
min=max1;
for(int j=1;j<=4;++j)
{
if(set[j]==0&&dist[j] {
v=j;
min=dist[j];
}
}
set[v]=1;
printf(“当前所用的中间的值：%dn”,v);
for(int j=1;j<=4;++j)
{
if(set[j]==0&&dist[v]+a[v][j] {
printf(“前一个：%d 数组：%d 相加：%d 现在：%dn”,dist[v],a[v][j],dist[v]+a[v][j],dist[j]);
dist[j]=dist[v]+a[v][j];
path[j]=v;
}
}
printf(“当前所改变的值：”);
for(int k=1;k<=4;k++)
{
printf("%d “,dist[k]);
}
printf(”n");
for(int k=1;k<=4;k++)
{
printf("%d “,path[k]);
}
printf(”n");
for(int k=1;k<=4;k++)
{
printf("%d “,set[k]);
}
printf(”n");
}
for(int i=1;i<=4;i++)
{
printf("%c:",i+‘A’);
fun(i);
printf("n");
}

}