java图论弗洛伊德和迪杰斯特拉算法解决最短路径问题

目录
  • 弗洛伊德算法
    • 算法介绍
    • 算法图解分析 
  •  迪杰斯特拉算法
    • 算法介绍
    • 算法过程 

弗洛伊德算法

算法介绍

算法图解分析 

 

 第一轮循环中,以A(下标为:0)作为中间顶点

【即把作为中间顶点的所有情况都进行遍历,就会得到更新距离表和前驱关系】,距离表和前驱关系更新为:

弗洛伊德算法和迪杰斯特拉算法的最大区别是:

弗洛伊德算法是从各个顶点出发,求最短路径;

迪杰斯特拉算法是从某个顶点开始,求最短路径。

/**
	 * 弗洛伊德算法
	 * 容易理解,容易实现
	 */
	public void floyd() {
		int len = 0;//变量保存距离
		//对中间顶点遍历,k就是中间顶点的下标[A,B,C,D,E,F,G]
		for(int k = 0;k < dis.length;k++) {
			//从i顶点开始出发[A,B,C,D,E,F,G]
			for(int i = 0;i < dis.length;i++) {
				//到达j顶点 //[A,B,C,D,E,F,G]
				for(int j = 0;j < dis.length;j++) {
					len = dis[i][k] + dis[k][j];//=>求出从i顶点出发,经过k中间顶点,到达j顶点距离
					if(len < dis[i][j]) {//如果len小于dis[i][j]
						dis[i][j] = len;//更新距离
						pre[i][j] = pre[k][j];//更新前驱顶点
					}
				}
			}
		}
	}

 迪杰斯特拉算法

算法介绍

算法过程 

public class DijkstraAlgorithm {
	public static void main(String[] args) {
		char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
		// 邻接矩阵
		int[][] matrix = new int[vertex.length][vertex.length];
		final int N = 65535;// 表示不可以连接
		matrix[0] = new int[] { N, 5, 7, N, N, N, 2 };
		matrix[1] = new int[] { 5, N, N, 9, N, N, 3 };
		matrix[2] = new int[] { 7, N, N, N, 8, N, N };
		matrix[3] = new int[] { N, 9, N, N, N, 4, N };
		matrix[4] = new int[] { N, N, 8, N, N, 5, 4 };
		matrix[5] = new int[] { N, N, N, 4, 5, N, 6 };
		matrix[6] = new int[] { 2, 3, N, N, 4, 6, N };
		// 创建Graph对象
		Graph graph = new Graph(vertex, matrix);
		// 测试,图的邻接矩阵是否ok
		graph.showGraph();
		// 测试迪杰斯特拉算法
		graph.dsj(6);
		graph.showDijkstra();
	}
}
class Graph {
	private char[] vertex;// 顶点数组
	private int[][] matrix;// 邻接矩阵
	private VisitedVertex vv;// 已经访问过的顶点的集合
	// 构造器
	public Graph(char[] vertex, int[][] matrix) {
		this.vertex = vertex;
		this.matrix = matrix;
	}
	// 显示结果
	public void showDijkstra() {
		vv.show();
	}
	// 显示图
	public void showGraph() {
		for (int[] link : matrix) {
			System.out.println(Arrays.toString(link));
		}
	}
	/**
	 * 迪杰斯特拉算法实现
	 *
	 * @param index 表示出发顶点对应的下标
	 */
	public void dsj(int index) {
		vv = new VisitedVertex(vertex.length, index);
		update(index);// 更新index顶点到周围顶点的距离和前驱顶点
		for (int j = 1; j < vertex.length; j++) {
			index = vv.updateArr();// 选择并返回新的访问顶点
			update(index);// 更新index顶点到周围顶点的距离和前驱顶点
		}
	}
	/**
	 * 更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点
	 */
	private void update(int index) {
		int len = 0;
		// 根据遍历邻接矩阵的 matrix[index]行
		for (int j = 0; j < matrix[index].length; j++) {
			// len含义是:出发顶点到index顶点的距离 + 从index顶点到j顶点的距离的和
			len = vv.getDis(index) + matrix[index][j];
			// 如果j顶点没有被访问过,并且len小于出发顶点到j顶点的距离,就需要更新
			if (!vv.in(j) && len < vv.getDis(j)) {
				vv.updateDis(j, index);// 更新j顶点的前驱为index顶点
				vv.updateDis(j, len);// 更新出发顶点到j顶点的距离
			}
		}
	}
}
//已访问顶点集合
class VisitedVertex {
	// 记录各个顶点是否访问过; 1表示访问过,0未访问,会动态更新
	public int[] already_arr;
	// 每个下标对应的值为前一个顶点下标,会动态更新
	public int[] pre_visited;
	// 记录出发顶点到其他所有顶点的距离,比如G为出发顶点,就会记录G到其他顶点的距离,动态更新,求的最短距离放到dis
	public int[] dis;
	/**
	 * 构造器
	 *
	 * @param length 表示顶点的个数
	 * @param index  出发顶点对应的下标,比如G顶点,下标就是6
	 */
	public VisitedVertex(int length, int index) {
		this.already_arr = new int[length];
		this.pre_visited = new int[length];
		this.dis = new int[length];
		// 初始化dis数组
		Arrays.fill(dis, 65535);
		this.already_arr[index] = 1;// 设置出发顶点被访问过
		this.dis[index] = 0;// 设置出发顶点的访问距离为0
	}
	/**
	 * 判断index顶点是否被访问过
	 *
	 * @param index
	 * @return 如果访问过,就返回true,否则返回false
	 */
	public boolean in(int index) {
		return already_arr[index] == 1;
	}
 	/**
	 * 更新出发顶点到index顶点的距离
	 *
	 * @param index
	 * @param len
	 */
	public void updateDis(int index, int len) {
		dis[index] = len;
	}
	/**
	 * 更新pre这个顶点的前驱顶点为index顶点
	 *
	 * @param pre
	 * @param index
	 */
	public void updatePre(int pre, int index) {
		pre_visited[pre] = index;
	}
	/**
	 * @return 返回出发顶点到index顶点的距离
	 */
	public int getDis(int index) {
		return dis[index];
	}
	public int updateArr() {
		int min = 65535, index = 0;
		for (int i = 0; i < already_arr.length; i++) {
			if (already_arr[i] == 0 && dis[i] < min) {
				min = dis[i];
				index = i;
			}
		}
		// 更新index顶点被访问过
		already_arr[index] = 1;
		return index;
	}
	// 显示最后的结果
	// 即将三个数组的情况输出
	public void show() {
		System.out.println("==========================");
		// 输出already_arr
		for (int i : already_arr) {
			System.out.print(i + " ");
		}
		// 输出pre_visited
		for (int i : pre_visited) {
			System.out.print(i + " ");
		}
		// 输出dis
		for (int i : dis) {
			System.out.print(i + " ");
		}
		System.out.println();
		// 为了好看最后的最短距离,如下处理
		char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
		int count = 0;
		for (int i : dis) {
			if (i != 65535) {
				System.out.print(vertex[count] + "(" + i + ")");
			} else {
				System.out.println("N");
			}
			count++;
		}
		System.out.println();
	}
}

以上就是java图论弗洛伊德和迪杰斯特拉算法解决最短路径问题的详细内容,更多关于弗洛伊德和迪杰斯特拉算法解决最短路径的资料请关注我们其它相关文章!

(0)

相关推荐

  • Java实现Floyd算法求最短路径

    本文实例为大家分享了Java实现Floyd算法求最短路径的具体代码,供大家参考,具体内容如下 import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class TestMainIO { /** * @param args * @throws FileNotFoundException */ public static void main(Stri

  • java实现Dijkstra最短路径算法

    任务描述:在一个无向图中,获取起始节点到所有其他节点的最短路径描述 Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止. Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表方式 用OPEN,CLOSE表的方式,其采用的是贪心法的算法策略,大概过程如下: 1.声明两个集合,open和close,open用于存储未遍历的节点,close用来存储

  • java实现dijkstra最短路径寻路算法

    [引用]迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径. 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止. 基本思想 通过Dijkstra计算图G中的最短路径时,需要指定起点s(即从顶点s开始计算). 此外,引进两个集合S和U.S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度),而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离). 初始时,S中只有起点s:U中是除s之外的顶点,并且U中顶点的路径是

  • 实现Dijkstra算法最短路径问题详解

    1.最短路径问题介绍 问题解释: 从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径,称为最短路径 解决问题的算法: 迪杰斯特拉算法(Dijkstra算法) 弗洛伊德算法(Floyd算法) SPFA算法 这篇博客,我们就对Dijkstra算法来做一个详细的介绍 2.Dijkstra算法介绍 算法特点: 迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题,算法最终得到一个最短路径树.该算法常用于路由算法或者作为其他图算法的一个子模块. 算法的思路 Dijk

  • Java 迪杰斯特拉算法实现查找最短距离的实现

    迪杰斯特拉算法 迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法.是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题.迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.具体的计算规则我们可以通过下图进行查看. 通过这幅图我们可以简单的理解迪杰斯特拉算法算法的基础思路,下面我们就通过JAVA来实现这个算法. 算法实现 在迪杰斯特拉算法中我们需要保存从起点开始到每一个节点最短步长,这也是图中需要比较得出的步长,同时我们还

  • java图论弗洛伊德和迪杰斯特拉算法解决最短路径问题

    目录 弗洛伊德算法 算法介绍 算法图解分析   迪杰斯特拉算法 算法介绍 算法过程  弗洛伊德算法 算法介绍 算法图解分析     第一轮循环中,以A(下标为:0)作为中间顶点 [即把作为中间顶点的所有情况都进行遍历,就会得到更新距离表和前驱关系],距离表和前驱关系更新为: 弗洛伊德算法和迪杰斯特拉算法的最大区别是: 弗洛伊德算法是从各个顶点出发,求最短路径: 迪杰斯特拉算法是从某个顶点开始,求最短路径. /** * 弗洛伊德算法 * 容易理解,容易实现 */ public void floyd

  • C++用Dijkstra(迪杰斯特拉)算法求最短路径

    算法介绍 迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法.是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题.迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低. 算法思想 按路径长度递增次序产生算法: 把顶点集合V分成两组: (1)S:已求出的顶点的集合(初始时只含有源点V0) (2)V-S=T:尚未确定的顶点集合 将T中顶点按递增

  • 详解Java中Dijkstra(迪杰斯特拉)算法的图解与实现

    目录 简介 工作过程 总体思路 实现 小根堆 Dijsktra 测试 简介 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等.注意该算法要求图中不存在负权边.对应问题:在无向图G=(V,E)中,假设每条边E(i)的长度W(i),求由顶点V0到各节点的最短路径. 工作过

  • C++实现Dijkstra(迪杰斯特拉)算法

    Dijkstra算法 Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,是广度优先算法的一种,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.其基本原理是:每次新扩展一个距离最短的点,更新与其相邻的点的距离.当所有边权都为正时,由于不会存在一个距离更短的没扩展过的点,所以这个点的距离永远不会再被改变,因而保证了算法的正确性.不过根据这个原理,用Dijkstra求最短路的图不能有负权边,因为扩展到负权边的时候会产生更短的距离,有可能就破

  • js图数据结构处理 迪杰斯特拉算法代码实例

    这篇文章主要介绍了js图数据结构处理 迪杰斯特拉算法代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 /*//1.确定数据结构, mapf[i][j] 为点i到点j的距离 [ Infinity 2 5 Infinity Infinity Infinity Infinity 2 6 Infinity Infinity Infinity Infinity 7 1 Infinity Infinity 2 Infinity 4 Infinity

  • Python实现迪杰斯特拉算法过程解析

    一. 迪杰斯特拉算法思想 Dijkstra算法主要针对的是有向图的单元最短路径问题,且不能出现权值为负的情况!Dijkstra算法类似于贪心算法,其应用根本在于最短路径的最优子结构性质. 最短路径的最优子结构性质: 如果P(i,j)={Vi-Vk-Vs-Vj}是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么P(k,s)必定是从k到s的最短路径. 证明: 假设P(i,j)={Vi-Vk-Vs-Vj}是从顶点i到j的最短路径,则有P(i,j)=P(i,k)+P(k,s)+P(s,j)

  • Python实现迪杰斯特拉算法并生成最短路径的示例代码

    def Dijkstra(network,s,d):#迪杰斯特拉算法算s-d的最短路径,并返回该路径和代价 print("Start Dijstra Path--") path=[]#s-d的最短路径 n=len(network)#邻接矩阵维度,即节点个数 fmax=999 w=[[0 for i in range(n)]for j in range(n)]#邻接矩阵转化成维度矩阵,即0→max book=[0 for i in range(n)]#是否已经是最小的标记列表 dis=[

  • java图论普利姆及克鲁斯卡算法解决最小生成树问题详解

    目录 什么是最小生成树? 普利姆算法  算法介绍 应用 --> 修路问题  图解分析  克鲁斯卡尔算法 算法介绍 应用场景 -- 公交站问题  算法图解   算法分析  如何判断是否构成回路 什么是最小生成树? 最小生成树(Minimum Cost Spanning Tree),简称MST. 最小生成树要求图是连通图.连通图指图中任意两个顶点都有路径相通,通常指无向图.理论上如果图是有向.多重边的,也能求最小生成树,只是不太常见. 普利姆算法  算法介绍 应用 --> 修路问题  图解分析 

  • 基于Python实现迪杰斯特拉和弗洛伊德算法

    图搜索之基于Python的迪杰斯特拉算法和弗洛伊德算法,供大家参考,具体内容如下 Djstela算法 #encoding=UTF-8 MAX=9 ''' Created on 2016年9月28日 @author: sx ''' b=999 G=[[0,1,5,b,b,b,b,b,b],\ [1,0,3,7,5,b,b,b,b],\ [5,3,0,b,1,7,b,b,b],\ [b,7,b,0,2,b,3,b,b],\ [b,5,1,2,0,3,6,9,b],\ [b,b,7,b,3,0,b,5

随机推荐