图论四 带权图的最短路径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");
			else
				System.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/