带权图 最短路径 代码自己写

 

最短路径问题

 

可能在带权图中，最常用遇到的问题就是，寻找两个点间的最短路径问题。

这个问题的解决方法可以应用在现实生活中很多情况，从印刷电路板到项目的调度都适合，但是它

比前面见到过的问题更负责一些，所以首先还是来看一个真是世界的场景，它还是发生在前面的引入的那个虚拟的国家

 

 

铁路线。

 

   这次我们来模拟的是铁路线而不是有线电路线了。然而，这个项目不像上一个那么浩大，这次并不是要修铁路

   而是铁路已经建好了。这次只是想找到从一个到另一个城市的最低费用

 

   旅客在两个城市间搭乘火车需要固定的费用。

    图的边是有方向的，也就是有向带权的。我们要最关心的是路费的便宜了。最类问题叫做最短路径问题。这里说说的最短

    并不一定只的是距离的最短，可能是费用的最少，时间的最少，效果的最好。、

 

    最便宜的费用

    任何两个城市间都有几条可能的路线，最短路径是这样的：

       对一个给定的原点和终止点，走哪条线路费用最低，带有向带权图

       正如前面提到的，铁路只有一个方向，所以火车在任何两个城市间只能朝一个方向进行。这相当于一个有向图，本来应该

       描述一个更接近现实的情况，也就是乘客可以花同样的钱在两个城市间往返。那就相当于一个无向图了。然而最短路径的问题

       在这两种情况下是类似的。所以为了体现多样性，我们来看这个问题在有向图中是怎样解决掉的

       

       

  Dijkstra 算法

 

    为了解决最短路径问题而提出来的方法叫做Dijkstra算法，Edsger Dijkstra在1959年解决了这个问题。

       这个算法是的实现是基于图的连接矩阵的表示法中的。让人感到有些惊奇的是它不仅仅能够找到任意两点间的最短路径，

      还可以找到某个指定点到其其他所有顶点的最短路径。

 

 代理人和铁路路线

 

 我们假设的要从a这个顶点开始，找到它到其他顶点的最低费用的路线。

 我们开始我们的想法了：

 

    在每个城市中，站长会告诉从该站到下一个站点的费用，也就是单程的费用。但是这个站长不知道，其他站的价格了。

    这里需要用到一个记事本，本子为每个城市留一列位子，并且希望每一列的最后显示从源点到其他城市的最低费用。

 

    第一个代理人：在A城市

     最终，需要再每个城市放一个代理人，这个代理人的工作就是保持到其他城市的信息费用的信息的。你自己就是A的代理人

   A城市站长所能告诉你的是到B城市的价格还有就是D城市的费用，把这些记录叜笔记本上，如果站长不知道，那么就记无限大。

      意味着不能从A到达表中的每一列的列头所示的城市，或者至少目前为止不知道如何到达那里。        （这个信息有用的，不要着急）

  规则

   总是把本站代理人的弟弟派到下一个城市去，从源点到这个城市的最低费用。一起到B城市去，在那里成成为了代理人。当他达到那里的时候，

   他将问站长到下一站 C 和 D的费用 其他是无线大

 

     经过简单的计算以后，从A到B到C的费用110，所以修改了在笔记本上的条目，从A经过B到D的费用是140元

     然而刚才知道了从A到D的费用是80元，由于值关心的是从A出发到目的地的最低费用，所以忽略这条最贵的路线了。笔记本上相应的条目也不做修改了

 

  在某个城市有代理人以后，可以确定的是这个代理人走过的路费是费用最低的路线。为什么呢？考虑现在的情况，如果有另一个线路比从A到B的直接

  连接更便宜，它需要通过其他的城市，但是从A厨房的另一条路线到D，它已经比到B的直接费用更加贵了。加上D到B的费用，使得这条费用更加贵了

 

 

  因此可以确定的是，从现在开始，不需要改动A到B的最低费用了，不管找到什么城市，这个费用都是不会变的。在它的旁边标注一个*号，表示在这个

  城市有一个代理人了，并且到它的最低费用是固定的。

 

 

 

       

         /**

	 * path()方法真正的执行了最短路径算法，它使用DisPar类和Vertex类，这个类在mstw.java程序
	 * 原点总是在vertxList[] 数组下标为0的位子，path()方法的第一个任务是把这个顶点放入树中，算法
	 * 执行过程中，将会把其他顶点也逐一放入树中。把顶点放入树中的操作是设置标志，并把nTree变量增加1，
	 * 这个变量记录了树中有多少个顶点。
	 * 
	 * 第二path()方法把邻接矩阵的对应行表达的距离的值复制到sPath[]中，实际总是先从第0行
	 * 复制，为了简单，假定源点的下标总为0，最开始，所有sPath[]数组中父节点字段为A，也就是源点。
	 *    现在进入算法的主要循环，等到所有的顶点都放入到树中，这个循环 就结束，这个循环中有是基本操作
	 *    
	 *    1. 选择sPath[]数组的最小距离
	 *    2. 把对应的顶点找出来（这个最小距离所在列的题头）放入树中，这个点变成当前的顶点，currentVer
	 *    3.根据currentVert的变化，更新所有的sPath[]数组的内容。
	 *如果path()方法发现最小距离是无穷大，它就知道有些顶点从源点不能到达。为什么？因为不是所有的顶点都是在树中
	 *（while 循环没有结束），尚无方法可以到达那些树外的顶点；如果有，就不会足无穷大了的距离了
	 *
	 *    返回前path()方法调用display显示 并且最后复位所有的顶点 
	 * 
	 *
	 *    
	 *    
	 * @return
	 */
	
	
	public int[] djisk() {
		
//		this.currentVetex = 0 ;
//		this.vertexList[0].setProxyer(true) ; //标记为设置了代理人的
//		
//		for (int i=currentVetex+1; i<this.nVertex; i++) {
//			
//			if(this.adjMat[currentVetex][i] == this.BIGGER) {
//				
//				this.sPath[i] = this.BIGGER ;
//				continue ;
//				
//			}
//			
//			this.sPath[i] = this.adjMat[]
//			
//			
//			
//		}
//		
//		
		
		
		
		return null ;
	}
	

 

 

 

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 

 

                          迪杰斯特拉（Dijkstra）

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 

 

 

创建边

package endual;

public class Edge {

	public int srcVert ; //一个顶点开始的序列好
	public int destVert ; //一个顶点结束的序号
	public int distance ;//从开始到介绍的长度
	
	public Edge(int srcVert, int destVert, int distance) {
		super();
		this.srcVert = srcVert;
		this.destVert = destVert;
		this.distance = distance;
	}
	
	
	
}

 

 

创建顶点


package endual;

public class Vertex {

	private char label;
	private boolean isInTree;

	public Vertex(char a) {
		this.label = a;
		this.isInTree = false;
	}

	public char getLabel() {
		return label;
	}

	public void setLabel(char label) {
		this.label = label;
	}

	public boolean isInTree() {
		return isInTree;
	}

	public void setInTree(boolean isInTree) {
		this.isInTree = isInTree;
	}

}

 

创建一个辅助的类

 

 

package endual;

public class DistPar {

	private int distance;
	private int parentVert;

	public DistPar(int distance, int parentVert) {
		super();
		this.distance = distance;
		this.parentVert = parentVert;
	}

	public int getDistance() {
		return distance;
	}

	public void setDistance(int distance) {
		this.distance = distance;
	}

	public int getParentVert() {
		return parentVert;
	}

	public void setParentVert(int parentVert) {
		this.parentVert = parentVert;
	}

}

 

创建一个图

 

其中path就是最短路径算法了

 

package endual;

public class Graph {

	private final int MAX_SIZE = 20;
	private final int INF = 1000000;
	private Vertex[] vertexList;
	private int adjMat[][];
	private int nVerts;
	private int nTree;
	private DistPar sPath[];
	private int currrentSize;
	private int startTOCurrent;
	private int currentVertex;

	public Graph() {

		super();
		this.vertexList = new Vertex[this.MAX_SIZE];
		this.adjMat = new int[this.MAX_SIZE][this.MAX_SIZE];
		initialAdjMat();
		this.nVerts = 0;
		this.nTree = 0;
		this.sPath = new DistPar[this.MAX_SIZE];
		this.currrentSize = 0;
		this.startTOCurrent = 0;

	}

	private void initialAdjMat() {

		for (int i = 0; i < this.MAX_SIZE; i++) {

			for (int j = 0; j < this.MAX_SIZE; j++) {

				this.adjMat[i][j] = this.INF;

			}
		}

	}

	// 插入顶点
	public void insert(char a) {

		Vertex v = new Vertex(a);
		this.vertexList[this.nVerts] = v;
		this.nVerts++;

	}

	// 插入边怎么没有边啊啊

	public void addEdge(int start, int end, int weight) {

		this.adjMat[start][end] = weight;

	}

	public void path() {

		int startTree = 0;
		this.vertexList[startTree].setInTree(true); // 已经放入到树中了
		this.nTree++;

		// 转换虫adjMat的列的长度到数组中去sPath
		for (int j = 0; j < this.nVerts; j++) {

			int tempDist = this.adjMat[startTree][j];
			DistPar tempDistPar = new DistPar(startTree, tempDist);
			sPath[j] = tempDistPar;

		}

		while (this.nTree < this.nVerts) {
			// 从sPath()中选择出边的长度最短的，这个getMin的是这个边的标号，最先的indexMin的标号
			int indexMin = getMin();
			//
			int minDist = this.sPath[indexMin].getDistance(); // 得到这个长度

			if (minDist == this.INF) {
				System.out.printf("None Edges");
				break;
			} else {

				currentVertex = indexMin; // 当前的顶点的在数组中的标号
				this.startTOCurrent = sPath[indexMin].getDistance(); // 当前顶点连接各个边的最短的长度
				// 最小的长度从开始的顶点开始的，转换到当前的顶点，然后

			}

			this.vertexList[this.currentVertex].setInTree(true); // 设置到树中了
			this.nTree++;
			adjust_sPath(); // 更新spathp[]数组

		} //end while 
		
		displayPaths() ;
		
		this.nTree = 0 ;
		for (int j=0; j < this.nVerts; j++) {
			
			this.vertexList[j].setInTree(false) ;
			
		}

	}

	//显示所有的最短路径
	private void displayPaths() {
		
		for (int i=0; i < this.nVerts; i++) {
			
			System.out.println(this.vertexList[i].getLabel()) ;
			if (this.sPath[i].getDistance() == this.INF) {
				
				System.out.println("Inf") ;
				
			}else {
				System.out.println(this.sPath[i].getDistance()) ;
			}
			char parent = this.vertexList[this.sPath[i].getDistance()].getLabel() ;
			System.out.print("{" + parent + "}") ;
			
		}
		System.out.println(" ") ;
	}

	private void adjust_sPath() {

		int column = 1 ;
		while (column  < this.nVerts) {
			
			if (this.vertexList[column].isInTree()) {			
				column++ ;
				continue ;	
			} // end if
			
			int currentToFringe = this.adjMat[this.currentVertex][column] ;
			int startToFrige = this.startTOCurrent + currentToFringe ;
			int sPathDist = this.sPath[column].getDistance() ;
			
			if (startToFrige < sPathDist) {
				
				this.sPath[column].setParentVert(currentVertex) ;
				this.sPath[column].setDistance(startToFrige) ;
			}
			column++ ;
			
			
		} //end while
		
		
	}

	private int getMin() {

		int minDist = this.INF;
		int indexMin = 0;

		for (int j = 1; j < this.nVerts; j++) {

			if (!this.vertexList[j].isInTree()
					&& this.sPath[j].getDistance() < minDist) {

				minDist = this.sPath[j].getDistance();
				indexMin = j;

			}

		}

		return indexMin;
	}

}