图论四 带权图的最短路径dijkstra
-- 图论写到这，基本概念也就告一段落了，之后还会贴一些我在工作中设计的图
--?图论一 ?http://blackproof.iteye.com/blog/1727050
--?图论二 ?http://blackproof.iteye.com/blog/1731542
--?图论二 ?http://blackproof.iteye.com/blog/1731557
--?图论三 ?http://blackproof.iteye.com/blog/1732941
--?感谢网上资料，感谢java数据结构和算法这本书。
?
求带权图的最短路径，经典算法是dijkstra算法
算法不仅可以求一个顶点到令一个顶点的最短路径，而且可以列出到所有节点的最短路径
?
算法思路
算法用一个数据存储当前所知道的最短路径spath[],
还用一个数据去存储已经遍历的节点V
?
遍历所有节点，将遍历的节点放入V，将起点到其他节点的权值放入spath[]中，并重复些列操作：
1.遍历的当前节点为currentVertex，取得spath[]中最小边，并将此边的终点作为当前节点
2.遍历当前节点到其他边的距离，并且用起点->当前顶点->其他没在V的顶点的值 和 spath[]中到对应终点的边做比较，当前者小，替代后者到spath中
当完成遍历后，spath中放置的就是从顶点到各个顶点的最短路径
?
代码如下：
? ?Graph：
package com.Construction.DiscrectGraph.Dijkstra;public class Graph {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;public Graph(){vertexList = new Vertex[MAX_VERTS];adjMat = new int[MAX_VERTS][MAX_VERTS];nVerts = 0;nTree = 0;for (int i = 0; i < MAX_VERTS; i++) {for (int j = 0; j < MAX_VERTS; j++) {adjMat[i][j] = 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;}public void path(){int startTree = 0;vertexList[startTree].isInTree = true;nTree = 1;for (int i = 0; i < nVerts; i++) {int tempDist = adjMat[startTree][i];sPath[i] = 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 i = 0; i < nVerts; i++) {vertexList[i].isInTree = false;}}public int getMin(){int minDist = INFINITY;int indexMin = 0;for (int i = 0; i < nVerts; i++) {if(!vertexList[i].isInTree && sPath[i].distance < minDist){minDist = sPath[i].distance;indexMin = i;}}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(){for (int i = 0; i < nVerts; i++) {System.out.println(vertexList[i].label + " = ");if(sPath[i].distance == INFINITY)System.out.println("int");elseSystem.out.println(sPath[i].distance);char parent = vertexList[sPath[i].parentVert].label;System.out.println("("+parent+")");}System.out.println();}public static void main(String[] args) {Graph theGraph = new Graph();theGraph.addVertex('A');theGraph.addVertex('B');theGraph.addVertex('C');theGraph.addVertex('D');theGraph.addVertex('E');theGraph.addEdge(0, 1, 50);theGraph.addEdge(0, 3, 80);theGraph.addEdge(1, 2, 60);theGraph.addEdge(1, 3, 90);theGraph.addEdge(2, 4, 40);theGraph.addEdge(3, 2, 20);theGraph.addEdge(3, 4, 70);theGraph.addEdge(4, 1, 50);System.out.println("shortest paths");theGraph.path();System.out.println();}}?
? ?算法中的spath中的对象：
? ?package com.Construction.DiscrectGraph.Dijkstra;
public class DistPar {public int distance;public int parentVert;public DistPar(int pv,int d){distance = d;parentVert = pv;}}?
? ?节点：
package com.Construction.DiscrectGraph.Dijkstra;public class Vertex {public char label;public boolean isInTree;public Vertex(char lab){label = lab;isInTree = false;}}??
感谢：http://2728green-rock.blog.163.com/blog/static/43636790200901211848284/
?