迪杰斯特拉算法求最短路径
有没有人能帮忙解释一下这个程序啊,里面很多变量都不知道是什么意思。谢谢。//定义常量和使用二维数组存储网
#include <stdio.h>
#define MAX 100 //表示两者之间的距离为无穷大
typedef int path[11][11],dist[11];
typedef int MGraph[11][11];
int q[11];
// R1, R2, R3, R4, R5, R6, N1, N2, N3, N4, N5
int arcs[11][11]={ 0,MAX,MAX, 8,MAX,MAX, 5,MAX,MAX,MAX,MAX, //R1
MAX, 0,MAX,MAX, 4,MAX, 7,MAX,MAX,MAX,MAX, //R2
MAX,MAX, 0,MAX,MAX,MAX, 3, 2,MAX,MAX,MAX, //R3
8,MAX,MAX, 0,MAX,MAX,MAX,MAX, 2,MAX,MAX, //R4
MAX, 4,MAX,MAX, 0,MAX,MAX,MAX, 5, 2,MAX, //R5
MAX,MAX,MAX,MAX,MAX, 0,MAX,MAX, 9,MAX, 5, //R6
0, 0, 0,MAX,MAX,MAX, 0,MAX,MAX,MAX,MAX, //N1
MAX,MAX, 0,MAX,MAX,MAX,MAX, 0,MAX,MAX,MAX, //N2
MAX,MAX,MAX, 0, 0, 0,MAX,MAX, 0,MAX,MAX, //N3
MAX,MAX,MAX,MAX, 0,MAX,MAX,MAX,MAX, 0,MAX, //N4
MAX,MAX,MAX,MAX,MAX, 0,MAX,MAX,MAX,MAX, 0}; //N5
//使用Dijkstra算法求R1到其它节点的最短路径
void ShortestPath(MGraph arc,int v0,path &P,dist &D)
{
int i,j,v,w,min;
int final[11];
for (v=0;v<11;++v)
{
final[v] = 0;
D[v]=arcs[v0][v]; //距离distance
for (w=0; w<11; ++w)
P[v][w] = 0; //路径path
if (D[v] <MAX)
{
P[v][v0] = 1;
P[v][v] = 1;
}
}
D[v0] = 0;
final[v0] = 1;
for (i=1; i<11; ++i)
{
min = MAX;
for (w=0; w<11; ++w)
if (!final[w])
if (D[w]<min)
{
v=w;
min=D[w];
}
final[v] = 1;
for (w=0; w<11; ++w)
if (!final[w] && (min+arcs[v][w]<D[w]))
{
D[w] = min + arcs[v][w];
q[w]=v;
for(j=0;j<11;j++)
P[w][j] = P[v][j];
P[w][w] = 1;
}
}
}
//主函数和打印最短路径和路由表
void main()
{
path p;
dist d;
int v0=0;
int i,j=0,r=22, a, b,temp=0, s1=5,arcs1[6][11];
char str[22]={'R','1','R','2','R','3','R','4','R','5','R','6','N','1','N','2','N','3','N','4','N','5'};
for (i=0;i<11;i++)
q[i]=v0;
for(i=0;i<6;i++)
for(j=0;j<11;j++)
arcs1[i][j]=MAX;
ShortestPath(arcs,v0,p,d);
for(i=6;i<11;i++)
{
a=q[i];
arcs1[i-6][10]=i;
for(j=9;j>0;j--)
{
if(a!=v0)
{
arcs1[i-6][j]=a;
a=q[a];
}
if(arcs1[i-6][j]==v0)
break;
}
}
printf ("\n路由器\t网络\t最短路径经过的路由器或网络\t最短路径值\n");
for(i=6;i<11;i++)
{
printf(" %c%c\t %c%c\t%c%c", str[v0*2], str[v0*2+1], str[2*i], str[2*i+1], str[v0*2], str[v0*2+1]);
for(j=0;j<11;j++)
{
if(arcs1[i-6][j]!=MAX&&arcs1[i-6][j]!=v0)
{
a=2*arcs1[i-6][j];
b=2*arcs1[i-6][j]+1;
printf("-%c%c",str[a],str[b]);
}
}
printf("\t\t\t\t%d\n",d[i]);
}
printf("\t\t网络\t下一路由器 \n");
for(i=6;i<11;i++)
{
printf("\t\t%c%c ",str[2*i],str[2*i+1]);
for(j=0;j<11;j++)
{
if(arcs1[i-6][j]!=MAX&&arcs1[i-6][j]!=v0&&arcs1[i-6][j]<6)
{
a=2*arcs1[i-6][j];
b=2*arcs1[i-6][j]+1;
printf("\t%c%c\n",str[a],str[b]);
temp=1;
break;
}
}
if(!temp)
printf("\t--\n");
}
}