`
endual
  • 浏览: 3566358 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

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

 
阅读更多

 

最短路径问题

 

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

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

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

 

 

铁路线。

 

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

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

 

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

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

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

 

    最便宜的费用

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

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

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

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

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

       

       

  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;
	}

}
 

 

 

 

分享到:
评论

相关推荐

    求带权图最短路径的代码

    在计算机科学中,求解图的最短路径...综上所述,求解带权图的最短路径涉及图的存储结构(如邻接矩阵和邻接表)和最短路径算法(如Dijkstra和Floyd-Warshall)。理解这些概念并能灵活运用,将有助于解决各种实际问题。

    最短路径算法Dijkstra源代码

    通常,测试会包括不同的输入,如单源最短路径、多源最短路径、包含环的图、具有大量节点和边的图等,以确保算法在各种情况下都能正确计算出最短路径。 在实际应用中,Dijkstra算法被广泛用于路由协议(如OSPF)、...

    图的最短路径、拓扑排序和关键路径

    在带权图中,图的最短路径问题是指从一个顶点到另一个顶点之间的路径中,所经过的边的权值之和最小的那条路径。 拓扑排序是图论中的一种重要概念,它是指将图中的顶点排序,使得从一个顶点到另一个顶点的路径中,所...

    dongtaiguihua.rar_matlab 最短路_动态最短_动态规划路径_动态路径_带权最短路径

    总的来说,"dongtaiguihua.rar"提供的MATLAB程序是动态规划应用于解决带权最短路径问题的一个实例,它展示了如何在实际问题中运用这一强大的工具。通过学习和理解这个程序,我们可以更好地掌握动态规划的精髓,以及...

    用贪心算法解单源最短路径问题

    1. 问题描述:求网(带权有向图)中从一个顶点到其余各顶点间的最短路径。 2. 实验原理:贪心算法原理。 3. 实验内容:使用贪心算法解决单源最短路径问题,并通过本例熟悉贪心算法在程序设计中的应用方法。 4. 实验...

    单源最短路径--分支限界法

    "单源最短路径--分支限界法" 单源最短路径是图论中的一种常见问题,它是指从一个源顶点到所有其他顶点的最短路径长度。这里的长度是指路上各边权之和。本文将介绍一种解决单源最短路径问题的方法,即分支限界法。 ...

    单源最短路径实验报告

    【单源最短路径】是图论中的一个重要概念,它是指在给定的带权有向图中,从一个特定的源节点出发,找到到达所有其他节点的最短路径。这个概念广泛应用于计算机科学和算法设计,特别是在网络路由、物流规划、社交网络...

    美国硅谷城镇地图——最短路径问题

    最短路径问题可以被定义为:在带权无向图或有向图中寻找两个特定节点间路径的最小代价。在这个硅谷城镇地图问题中,我们可以假设图是有向的,因为通常交通网络都是单向的。权值可能代表距离、行驶时间或者其它相关的...

    C#实现最短路径算法

    2. **Floyd-Warshall算法**:这是一个解决所有对最短路径问题的动态规划方法,适合处理带权的有向图或无向图。Floyd-Warshall算法通过逐步更新所有节点对之间的最短路径,最终得到完整的最短路径矩阵。C#实现时,...

    Dijkstra算法寻找最短路径的完整源代码

    "Dijkstra算法寻找最短路径的完整源代码" 本资源提供了Dijkstra算法寻找最短路径的完整源代码,同时附带了Kruskal最小生成树算法。该程序提供了输入输出的完整控制台程序,能够帮助用户快速了解和应用Dijkstra算法...

    floyd_floyd最短路径算法_最短路径矩阵_最短路径_只需要改邻接矩阵_

    - **Floyd算法,只需改带权邻接矩阵.txt**:暗示文件可能包含使用Floyd算法的示例代码或步骤说明,其中重点关注如何通过修改带权重的邻接矩阵来求解最短路径。 综上,Floyd算法是一种强大的图论工具,用于找出所有...

    从某个源点到其于各顶点的最短路径

    - 单源最短路径问题的目标是:给定一个带权有向图G=(V,E),其中V为顶点集,E为边集,每条边(e)有一个非负的权重cost(e),以及一个特定的顶点s(源点),找到从s到每个其他顶点v的最短路径。 #### 三、算法实现分析...

    python实现有向图单源最短路径迪杰斯特拉 算法

    迪杰斯特拉(Dijkstra)算法是一种用于寻找有向图中单源最短路径的经典算法,由荷兰计算机科学家艾兹格·迪杰斯特拉在1956年提出。在这个算法中,我们从一个源节点开始,逐步扩展最短路径到其他节点,直到到达所有...

    分支限界法-单源最短路径

    **单源最短路径问题**的目标是在一个带权的有向图中找到从一个指定的源点到图中其他所有顶点的最短路径。这里的权重是指图中边的成本或代价,通常是非负的。 #### 四、算法设计 在解决单源最短路径问题时,可以...

    用Dijkstra算法求图中单源最短路径

    "用Dijkstra算法求图中单源最短路径" Dijkstra算法是一种常用的图搜索算法,用于解决单源最短路径问题。单源最短路径问题是指从一个出发顶点到所有可达顶点的最短路径问题。Dijkstra算法的原理是通过将图中的每个...

    基于贪心法求解单源最短路径问题.docx

    "基于贪心法求解单源最短路径问题" 本资源是关于基于贪心法求解单源最短路径问题的实验报告,包括实验内容、算法设计、算法描述、算法正确性证明、算法分析、算法实现与测试等部分。 实验目的:理解贪心法的核心...

    带权无向网求最短路径

    在IT领域,尤其是在图论和算法设计中,"带权无向网求最短路径"是一个重要的主题。这个任务涉及到如何在没有方向的网络中,从一个特定的起点找到到达所有其他点的最短路径。这通常应用于各种场景,如交通路线规划、...

    k-最短路径

    《MATLAB实现K-最短路径算法详解》 在图论和计算机科学中,K-最短路径(K-Shortest Paths,KSP)是一种寻找网络中从源节点到目标节点多条最短路径的算法。它扩展了单源最短路径问题,不仅找出一条最短路径,而是...

    Floyd算法求任意两点间的最短路径

    用C++ 语言编写 用Floyd算法求有向图中任意两点间的最短路径 由用户输入顶点和有向边的信息

    贪心算法法-单源最短路径 java

    本篇文章探讨的是在给定的带权有向图 \(G=(V,E)\) 中,利用贪心算法求解单源最短路径问题的方法。具体来说,问题可以这样描述:在一个带权有向图 \(G=(V,E)\) 中,每条边都有一个非负整数权重(这里简化为整数)。...

Global site tag (gtag.js) - Google Analytics