跪求有向图的最短路径问题

Question

哥哥们啊，帮忙看看：
package 有向图的最短路径;
class  DisPar//distance,parentvert
{
int distance ;
int parentvert;
DisPar(int d,int p)
{
distance=d;
parentvert=p;
}
}
class vertex
{
char label;
boolean isintree;
vertex(char lab)
{
label=lab;
isintree=false;
}
}
class Graph
{
vertex vlist[];
DisPar spath[];
final int maxverts=20;
int adjmax[][];
int ntree;
final int infinity=1000;
int nverts;
int currentvert;
int starttocurrent;
Graph()
{
vlist=new vertex[maxverts];
adjmax=new int[maxverts][maxverts];
for(int m=0;m<maxverts;m++)
for(int n=0;n<maxverts;n++)
adjmax[m][n]=infinity;
ntree=0;
nverts=0;
spath=new DisPar[maxverts];
}
void addvertex(char lab)
{
vlist[nverts++]=new vertex(lab);
}
void addedge(int start,int end,int distance)
{
adjmax[start][end]=distance;
}
int getMin()
{
int indexMin=0;
for(int m=0;m<nverts;m++)
{
if(!vlist[m].isintree&&spath[m].distance<infinity)
indexMin=m;
}
return indexMin;
}
void path()//从任意一个顶点到其他顶点的最短路径
{
int starttree=0;
vlist[starttree].isintree=true;
ntree=1;
for(int i=0;i<nverts;i++)
{
spath[i]=new DisPar(i,adjmax[starttree][i]);
}
while(ntree<nverts)
{
int indexMin=getMin();
int minDist=spath[indexMin].distance;
if(minDist==infinity)
{
System.out.println("There are not reachable path");
break;
}
else
{
currentvert=indexMin;
starttocurrent=minDist;
}
vlist[currentvert].isintree=true;
ntree++;
adjust_path();//重新更新树
}
display_paths();//显示路径
ntree=0;
for(int j=0;j<nverts;j++)
vlist[j].isintree=false;
}
void adjust_path()//更新函数
{
int column=1;
while(column<nverts)
{
if(vlist[column].isintree)
{
column++;
continue;
}
int CurrentToFringe=adjmax[currentvert][column];
int StartToFringe=starttocurrent+CurrentToFringe;
int sPathDist=spath[column].distance;
if(StartToFringe<sPathDist)
{
spath[column].parentvert=currentvert;
spath[column].distance=StartToFringe;
}
column++;
}
}
void display_paths()
{
for(int j=0;j<nverts;j++)
{
System.out.println(vlist[j].label+"=");
if(spath[j].distance==infinity)
System.out.println("inf");
else
System.out.print(spath[j].distance);
char parent=vlist[spath[j].parentvert].label;
System.out.print("("+parent+")");
}
System.out.println();
}
}
class testpath
{
public static void main(String[] args)
{
Graph g=new Graph();
g.addvertex('A');
g.addvertex('B');
g.addvertex('C');
g.addvertex('D');
g.addvertex('E');
g.addedge(0,1,50);
g.addedge(0,3,80);
g.addedge(1,2,60);
g.addedge(1,3,90);
g.addedge(3,4,70);
g.addedge(4,1,50);
g.addedge(2,4,40);
g.addedge(3,2,20);
g.path();
g.display_paths();
}
}
在EditPlus里面编译没问题，可是，运行的时候，提示：E:\java\rubbish\DataStructure>java 有向图的最短路径.testpath
A=
0Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 1000
        at 有向图的最短路径.Graph.display_paths(DisPar.java:124)
        at 有向图的最短路径.Graph.path(DisPar.java:89)
        at 有向图的最短路径.testpath.main(DisPar.java:148)
帮忙啊，兄弟多谢了。

Answer 1

此回复为自动发出,仅用于显示而已，并无任何其他特殊作用
楼主【fwloveyou】截止到2008-08-03 17:47:33的历史汇总数据(不包括此帖)：
发帖的总数量:20                       发帖的总分数:140                      每贴平均分数:7                        
回帖的总数量:6                        得分贴总数量:0                        回帖的得分率:0%                       
结贴的总数量:19                       结贴的总分数:110                      
无满意结贴数:16                       无满意结贴分:470                      
未结的帖子数:1                        未结的总分数:30                       
结贴的百分比:95.00 %               结分的百分比:78.57 %                  
无满意结贴率:84.21 %               无满意结分率:427.27%                  
值得尊敬
取消马甲机器人，请点这里：http://www.java2000.net/mycsdn/robotStop.jsp?usern=fwloveyou

Answer 2

那我为什么得不到自己想要的结果呢？
g.addvertex('A');
g.addvertex('B');
g.addvertex('C');
g.addvertex('D');
g.addvertex('E');
g.addedge(0,1,50);
g.addedge(0,3,80);
g.addedge(1,2,60);
g.addedge(1,3,90);
g.addedge(3,4,70);
g.addedge(4,1,50);
g.addedge(2,4,40);
g.addedge(3,2,20);
，输出应该是
A=inf(A) B=50(A) C=100(D) D=80(A) E=140(c)才对呀，
是不是path()里面，查了老半天找不到原因