在带权图中最常遇到的问题就是，寻找两点间的最短路径问题。
解决最短路径问题最著名的算法是Djikstra算法。这个算法的实现基于图的邻接矩阵表示法，它不仅能够找到任意两点的最短路径，还可以找到某个指定点到其他所有顶点的最短路径。
此算法的基本思想是：
1> 选中指定的顶点，列出此顶点到其他的顶点的权值，不相邻的为无穷大
2> 从以上权值中选出最小值，此最小值就是起始点到对应顶点的最短路径，并标记这个对应顶点
3> 将起始点到其他未标记的顶点的直接距离与起始点到刚才标记顶点加上标记顶点到其他顶点距离的和比较，如果 后者小，则更新对应的权值。
4> 转2
此算法的java实现如下：
class DistPar...{
public int distance; public int parentVert;
public DistPar(int pv,int d)...{ distance=d; parentVert=pv;
}
}
class Vertex...{ public char label; public boolean isInTree; public Vertex(char lab)...{ label=lab; isInTree=false; }}public class Path ...{ private final int MAX_VERTS=20; private final int INFINITY=1000000; private Vertex vertexList[]; private int adjMat[][]; private int nVerts; private int nTree; private DistPar sPath[]; private int currentVert; private int startToCurrent; /** *//** Creates a new instance of Path */ public Path() ...{ vertexList=new Vertex[MAX_VERTS]; adjMat=new int[MAX_VERTS][MAX_VERTS]; nVerts=0; nTree=0; for (int j = 0; j < MAX_VERTS; j++) ...{ for (int k = 0; k < MAX_VERTS; k++) ...{ adjMat[j][k]=INFINITY; } } sPath=new DistPar[MAX_VERTS]; } public void addVertex(char lab)...{ vertexList[nVerts++]=new Vertex(lab); } public void addEdge(int start,int end,int weight)...{ adjMat[start][end]=weight; } //找到选定顶点到其他顶点的最短路径(此处选定0号顶点) public void path()...{ int startTree=0; vertexList[startTree].isInTree=true; nTree=1; for(int j=0;j<nVerts;j++)...{ int tempDist=adjMat[startTree][j]; sPath[j]=new DistPar(startTree,tempDist); } while(nTree<nVerts)...{ int indexMin=getMin(); int minDist=sPath[indexMin].distance; if(minDist==INFINITY)...{ System.out.println("There are unreachable vertices"); break; }else...{ currentVert=indexMin; startToCurrent=sPath[indexMin].distance; } vertexList[currentVert].isInTree=true; nTree++; adjust_sPath(); } displayPaths(); nTree=0; for (int j = 0; j < nVerts; j++) ...{ vertexList[j].isInTree=false; } } //得到当前最短路径数组中的最小值 public int getMin()...{ int minDist=INFINITY; int indexMin=0; for (int j = 1; j < nVerts; j++) ...{ if(!vertexList[j].isInTree&&sPath[j].distance<minDist)...{ minDist=sPath[j].distance; indexMin=j; } } return indexMin; } //更新最短路径数组 public void adjust_sPath()...{ int column=1; while(column<nVerts)...{ if(vertexList[column].isInTree)...{ column++; continue; } int currentToFringe=adjMat[currentVert][column]; int startToFringe=startToCurrent+currentToFringe; int sPathDist=sPath[column].distance; if(startToFringe<sPathDist)...{ sPath[column].parentVert=currentVert; sPath[column].distance=startToFringe; } column++; } } public void displayPaths()...{ } }
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
