最短路径的Dijkstra算法.doc

====实****报告二 “最短路径的Dijkstra算法”演示程序 =====
、程序的功能和特点
1. 程序功能：建立带权网图的邻接矩阵，用Dijkstra算法算出任一点到其它点的最短路径及其显示路线。
2. 程序特点：采用java*/
if(dist[v]<MaxValue&&v!=v0) path[v]=v0;
else path[v]=-1; /* 无直达路径 */
}
/*初始时源点v0∈S集，表示v0到v0的最短路径已经找到*/
dist[v0]=0;s[v0]=1;
//下来假设经由一个点中转到达其余各点,会近些,验证之.
//再假设经由两个点中转,会更近些,验证之,.....
//直到穷举完所有可能的中转点.
double min;
for(i=1;i<CurrentVertices ;i++) {
//挑一个距离最近经由点,下标装入v
min=MaxValue;
for(w=0;w<CurrentVertices;w++)
/*顶点w不属于S集且离v0更近*/
if(s[w]==0 && dist[w]<min){
v=w; /* 经由顶点w中转则距离更短 */
min=dist[w];
}
s[v]=1; /*顶点v并入S，
由v0到达v顶点的最短路径为min*/
/*假定由v0到v，再由v直达其余各点，
更新当前最后一个经由点及距离*/
for(j=0;j<CurrentVertices;j++)
if(s[j]==0 && (min+Edge[v][j]<dist[j])){
/* 如果多经由一个v点到达j点的
最短路径反而要短,就更新.*/
dist[j]=min+Edge[v][j];
path[j]=v; /* 经由点的序号 */
}/*if*/
}/*循环for i */
}/*Dijkstra算法结束*/
（三）、程序中类的设计
“GraphPath ”类：
【逻辑结构与存储结构】
逻辑结构：线性结构。 存储结构：顺序存储结构。
所谓邻接矩阵（Adjacency Matrix）的存储结构，就是用一维数组存储图中顶点的信息，用矩阵表示图中各顶点之间的邻接关系。假设图G＝（V，E）有n个确定的顶点，即V＝{v
0,v1,…,vn-1},则表示G中各顶点相邻关系为一个n×n的矩阵，矩阵的元素为：
{
若(vi,vj)或<vi,vj>是E(G)中的边
0 若(vi,vj)或<vi,vj>不是E(G)中的边
A[i][j]=
若G是网图，则邻接矩阵可定义为：
{
wij 若(vi,vj)或<vi,vj>是E(G)中的边
0或∞ 若(vi,vj)或<vi,vj>不是E(G)中的边
A[i][j]=
其中，wij表示边(vi,vj)或<vi,vj>上的权值；∞表示一个计算机允许的、大于所有边上权值的数。
用邻接矩阵表示例如下图。
V3
V0
3
0 1 0 1
A＝ 1 0 1 1
V1
V2
0 1 0 0
1 0 0

一个无向图的邻接矩阵表示
0
9 6 ∞ 9 6 3 ∞
2
1
3 9 ∞ 4 5 ∞
4 A＝ 6 4 ∞ ∞ 7
5 7 3 5 ∞ ∞ 8
8
4
3