数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。

这篇具有很好参考价值的文章主要介绍了数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

  • 最短路径的算法有两个,Dijkstra算法 和 Floyd算法
  • Dijkstra算法 解决的是 单源 最短路径问题
  • Floyd算法解决的是 多源 最短路径问题,并且可以处理负权图
  • 今天要讲的就是Dijkstra算法。
  • 加:feng--Insist(大写的i),进java交流群讨论互联网+技术。可索要PPT等资料。
  • 其他资料,建议先看本篇博客。:Dijkstra算法和Floyd算法:https://blog.csdn.net/weixin_43872728/article/details/100662957
  • 代码位置:https://github.com/fengfanli/dataStructuresAndAlgorithm/tree/master/src/com/feng/algorithm/self_learn

一、单源最短路径

1、单源最短路径问题

  • 解决的问题: 求解单源最短路径,即各个节点到达源点的最短路径或权值。如下图中
    数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。,数据结构与算法,算法,java,开发语言
    考察其他所有节点到源点的最短路径和长度
  • 局限性: 无法解决权值为负数的情况
  • 资料
    • 可先看匹配视频:https://www.bilibili.com/video/BV1o44y1B7NM/
    • 代码:待上传。

2、Dijkstra 初始化

首先已知的是:
给定 邻接矩阵表示的图Graph、源点S、终点T

a、参数

参数:

参数名 解释
S 记录当前已经处理过的源点到最短节点
U 记录还未处理的节点
dist[] 记录各个节点到起始节点的最短权值
path[] 记录各个节点的上一级节点(用来联系该节点到起始节点的路径)

b、初始化参数

  • 顶点集S: 节点A到自已的最短路径长度为0。只包含源点,即S={A},代码中没有这个,这里是为了步骤清晰而设置的。
  • 顶点集U: 包含除A外的其他顶点. 即U={B,C,D,E,F,G}
  • dist[]: 源点还不能到达的节点,其权值为∞
A B C D E F G
dist[]: 0 1 2 3 4 5 6
初始化值: 0 4 6 6

path[]: 记录当前节点的前驱节点下标(源点还不能到达的节点为-1)

A B C D E F G
path[]: 0 1 2 3 4 5 6
初始化值: 0 0 0 0 -1 -1 -1

c、算法步骤

数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。,数据结构与算法,算法,java,开发语言

  1. 初始化:设定除源节点以外的其它所有节点到源节点的距离为INFINITE(一个很大的数),且这些节点都没被处理过。如上图所示
  2. 从源节点出发,更新相邻节点(图中为B、C、D)到源节点的距离。然后在所有节点中选择一个最段距离的点作为当前节点。
  3. 标记当前节点为done(表示已经被处理过),与步骤2类似,更新其相邻节点的距离。(这些相邻节点的距离更新也叫 松弛,目的是让它们与源节点的距离最小。因为你是在当前最小距离的基础上进行更新的,由于当前节点到源节点的距离已经是最小的了,那么如果这些节点之前得到的距离比这个距离大的话,我们就更新它)。
  4. 步骤3做完以后,设置这个当前节点已被done,然后寻找下一个具有最小代价(cost)的点,作为新的当前节点,重复步骤3.
  5. 如果最后检测到目标节点时,其周围所有的节点都已被处理,那么目标节点与源节点的距离就是最小距离了。如果想看这个最小距离所经过的路径,可以回溯,前提是你在步骤3里面加入了当前节点的最优路径前驱节点信息。
  • 我总结了下可用如下几句话代替:
    两步走
    1. 从dist[]中在集合U中的选择最小距离加入到S中,作为当前节点。(最小距离:就是 当前节点到源点的最小距离)
    2. 遍历当前节点的邻边节点:更新dist[]和path[]
      • 如果经过当前节点+邻边权重 < 邻边节点,则改变dist[]和path[],否者不改变。

3、Dijkstra 算法详细步骤

a、第一轮算法执行

数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。,数据结构与算法,算法,java,开发语言

  • 如上图,因为dist[]中排出掉集合U中节点,最小值是4,也就是节点B,所以将B纳入到集合S中(圈中)。

  • 首先 在dist[]数组中并在集合U中 最小值是节点B,既当前节点,其邻边有C和E,所以看是否要更新C和E。

    • 节点C:因为C的最小距离dist[1](B的最小距离)4+1(B到C的距离)=5 < dist[2](C的最小距离) = 6,所以 dist[2]=5,path[2]=1
    • 节点E:因为E的最小距离 dist[1](B的最小距离)4+7(B到E的距离)=11 < dist[4] (E的最小距离)=无穷大,所以 dist[4]=11,path[4]=1
  • 第一轮算法两个邻边节点C、E有改变

b、第二轮算法执行

数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。,数据结构与算法,算法,java,开发语言

  • 如上图,因为dist[]中排出掉集合U中节点,最小值是5,也就是节点C,所以将C纳入到集合S中(圈中)。
  • 首先在dist[]数组中并在集合U中 最小值是节点C,既当前节点,其邻边有E和F,所以看是否要更新E和F。
    • 节点E:因为C的最小距离 dist[2](也就是C的最小距离)5+6(C到E的距离)=11 == dist[4](E的最小距离) = 11,所以不动
    • 节点F:因为F的最小距离 dist[2](也就是C的最小距离)5+4(C到F的距离)=9 < dist[5] (F的最小距离)=无穷大,所以 dist[5]=9,path[5]=2
  • 第二轮算法两个邻边节点仅有 F有改变

c、第三轮算法执行

数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。,数据结构与算法,算法,java,开发语言

  • 如上图,因为dist[]中排出掉集合U中节点,最小值是6,也就是节点D,所以将D纳入到集合S中(圈中)。
  • 首先在dist[]数组中并在集合U中 最小值是节点D,既当前节点,其邻边有C和F,所以看是否要更新C和F。
  • 节点C:因为C的最小距离 dist[3](也就是D的最小距离)6+2(D到C的距离)=8 > dist[2](C的最小距离) = 5 ,所以不动
  • 节点F:因为F的最小距离 dist[3](也就是D的最小距离)6+5(D到F的距离)=11 > dist[5] (F的最小距离)=9,所以不动
  • 第三轮算法两个邻边节点C、F都没有改变

d、第四轮算法执行

数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。,数据结构与算法,算法,java,开发语言

  • 如上图,因为dist[]中排出掉集合U中节点,最小值是9,也就是节点F,所以将F纳入到集合S中(圈中)。
  • 首先在dist[]数组中并在集合U中 最小值是节点F,既当前节点,其邻边有E和G,所以看是否要更新E和G 。
  • 节点E:因为E的最小距离 dist[5](也就是F的最小距离) 9 +1(F到E的距离)=10 < dist[4](E的最小距离) =11,所以 dist[4] = 10,path[4]=5
  • 节点G:因为G的最小距离 dist[5](也就是F的最小距离) 9 +8(F到G的距离)=17 < dist[6](G的最小距离) =无穷大,所以 dist[6]=17,path[6]=5
  • 第四轮算法两个邻边节点E、G都有改变

e、第五轮算法执行

数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。,数据结构与算法,算法,java,开发语言

  • 如上图,因为dist[]中排出掉集合U中节点,最小值是9,也就是节点F,所以将F纳入到集合S中(圈中)。
  • 首先在dist[]数组中并在集合U中 最小值是节点E,既当前节点,其邻边有G,所以看是否要更新G
  • 节点G:因为G的最小距离 dist[4](也就是E的最小距离) 10 +6(E到G的距离)=16 < dist[6](G的最小距离) =17,所以 dist[6]=16,path[6]=4
  • 第五轮算法邻边 节点G有改变

f、第六轮算法执行

数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。,数据结构与算法,算法,java,开发语言

  • 如上图,因为dist[]中排出掉集合U中节点,最小值是16,也就是节点G,所以将G纳入到集合S中(圈中)。
  • 首先在dist[]数组中并在集合U中 最小值是节点G,既当前节点,其没有邻边。
  • 第六轮算法邻边节点G没有改变
  • 到此算法遍历结束

4、java算法实现

给定矩阵表示的Graph结构。输入源点v0和终点v1。


二、多源最短路径

1、多源最短路径问题

  • 上面的Dijkstra 解决的是单源最短路径的问题,首先要给定 开始节点和终止结点,如果换了开始和终止节点,那就要每次都要重新跑一次。
  • 那就引出了多源最短路径问题:就是执行一次算法,求出每两个点之间的最短距离,这就是多源最短路径算法。这个算法代码略简单一些。
  • 思想只有一个:要算两个点之间的最短距离,就看有没有第三个点使得

2、Floyd初始化

首先已知的是:
给定 **邻接矩阵表示的图Graph。文章来源地址https://www.toymoban.com/news/detail-672285.html

a、参数

参数名 解释
A[][] 函数中的参数,需要返回,存储的是节点的前置节点。
path[][] 存储的是每两点之间的所需距离。

b、参数初始化

参数名 解释
A[][] 就是图的赋值,从代码中可以看出,比较简单
path[][] 默认都是-1.表示从A点到B点是直达的。

c、算法步骤

  1. 对于每个顶点v(体现在代码的第一层for循环),和任意一顶点(i,j)(体现代码的第二、三层循环),切 i!=j、v!=i、v!=j
  2. 如果A[i][j] > A[i][v] + A[]v[j],则将A[i][j] 更新为 A[i][v] + A[v][j] 的值,并且将path[i][j]改为v

3、Floyd算法详细步骤

4、java 算法实现

package com.feng.algorithm.self_learn.floyd.floyd1;

/**
 * 学习视频:https://www.bilibili.com/video/BV1LE411R7CS
 */
public class FloydAlgorithm {
    public static void main(String[] args) {
        int[][] graph = new int[4][4];
        int N = Short.MAX_VALUE;
        graph[0] = new int[]{0, 5, N, 7};
        graph[1] = new int[]{N, 0, 4, 2};
        graph[2] = new int[]{3, 3, 0, 2};
        graph[3] = new int[]{N, N, 1, 0};

        int[][] path = new int[4][4];
        int[][] A = Floyd.floyd(graph, path);
        int u = 1;
        int v = 0;
        Floyd.printPath(u, v, path);
        System.out.println();
        System.out.println(u + "->" + v +" shortest path is :" + A[u][v]);
    }
}
class Floyd {

    /**
     * 佛洛依德算法,给定邻接矩阵表示的图,
     * path[][]:存放路径中间的节点,如果是-1就是直达
     * A[][]:存放任意两个节点之间的距离
     * 举例:从1-0,从A得出距离是6,从path得出 1-3-2-0
     * @param graph
     * @param path
     */
    static int[][] floyd(int[][] graph, int[][] path) {
        int n = graph.length;
        int v, i, j;
        int[][] A = new int[n][n];
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                A[i][j] = graph[i][j];
                path[i][j] = -1;
            }
        }

        for (v = 0; v < n; v++) {
            for (i = 0; i < n; i++) {
                for (j = 0; j < n; j++) {
                    if (A[i][j] > A[i][v] + A[v][j]) {
                        A[i][j] = A[i][v] + A[v][j];
                        path[i][j] = v;
                    }
                }
            }
        }
        return A;
    }

    /**
     * 递归打印路径
     * @param u
     * @param v
     * @param path
     */
    static void printPath(int u, int v, int[][] path) {
        if (path[u][v] == -1) { // 如果等于 -1 。说明就是直达的
            System.out.printf(u + "->" + v + " ");
        } else {
            int mid = path[u][v];
            printPath(u, mid, path);
            printPath(mid, v, path);
        }
    }
}


到了这里,关于数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C语言数据结构——图的最短路径算法解决实例问题

    一、问题描述 W公司在某个地区有6个产品销售点,现根据业务需要打算在其中某个销售点上建立一个中心仓库,负责向其他销售点提供产品。由于运输线路不同,运输费用也不同。假定每天需要向每个销售点运输一次产品,那么应将中心仓库建在哪个销售点上,才能使运输费

    2024年02月08日
    浏览(47)
  • 数据结构 -最短路径dijkstra(迪杰斯特拉)算法讲解及代码实现

            迪杰斯特拉算法是一种广义的贪心算法,求出局部最优解,再去求全局最优解 举例图:(起始点为1) 辅助数组: s:记录了目标顶点到其他顶点的最短路径是否求得(求得为1,否则为0) p:目标顶点到其他顶点的最短路径的前驱节点 (如,求得1-7-5的最短路径,那

    2024年02月11日
    浏览(38)
  • 数据结构实验任务六 :基于 Dijsktra 算法的最短路径求解

    本次代码为实验六:基于 Dijsktra 算法的最短路径求解实现。本实验的重点在于对于Dijsktra算法的理解。有关Dijsktra的资料可以参考有关博文: 图论:Dijkstra算法——最详细的分析,图文并茂,一次看懂!-CSDN博客 以下附上实现代码: 以上代码仅供参考,欢迎交流。

    2024年02月04日
    浏览(50)
  • 数据结构学习记录——图-最短路径问题(无权图单源最短路径算法、有权图单源最短路径算法、多源最短路径算法、Dijkstra(迪杰斯特拉)算法、Floyd算法)

    目录 问题分类  无权图单源最短路径算法 思路 伪代码 时间复杂度 代码实现(C语言) 有权图单源最短路径算法 Dijkstra(迪杰斯特拉)算法 伪代码  时间复杂度  代码实现(C语言) 多源最短路径算法 两种方法 Floyd算法 代码实现(C语言) 最短路径问题的抽象 在网络中,求

    2024年02月08日
    浏览(58)
  • 数据结构与算法 —— 最短路径Dijkstra算法(迪杰斯特拉)详细图解以及python实现

    目录 前言 1. 介绍 2. 加权图 2.1 概念 3. 最短路径 -- Dijkstra 算法 3.1 历史 3.2 Dijkstra 算法的基本思路 3.3 Dijkstra 算法图解 4.  python中dijkstra算法的实现 5. 总结  前两章我们讲到了关于图的基本知识,和广度/深度优先搜索。 本章,我们将介绍 加权图 和 最短路径 的相关知识。 最

    2024年02月12日
    浏览(52)
  • 数据结构(12)Dijkstra算法JAVA版:图的最短路径问题

    目录 12.1.概述 12.1.1.无权图的最短路径  12.1.2.带权图的最短路径 1.单源最短路径 2.多源最短路径 12.2.代码实现 无权图的最短路径,即最少步数,使用BFS+贪心算法来求解最短路径,比较好实现,此处不做展开讨论。 有权图的最短路径,不考虑权重为负数的情况,因为权重为负

    2024年02月06日
    浏览(47)
  • C语言算法与数据结构,旅游景区地图求最短路径

    本次作业要求完成一个编程项目。请虚构一张旅游景区地图,景区地图包括 景点(结点)和道路(边):地图上用字母标注出一些点,表示景点(比如,以点 A、B、C、D、E、F等(至少6个点)多个表示,其中的 两个字母 A 和 B 分别表示景区的入口和出口 );点与点之间的连

    2024年02月04日
    浏览(44)
  • C++ | 数据结构与算法 | 单源最短路径 | Dijkstra && Bellman Ford

    (关于代码实现的图结构,可以看图结构的实现这篇文章) Dijkstra的实现与Prim的实现相似,两者都是通过贪心思想实现,它们有什么不同呢?首先Prim算法是针对无向图的最小生成树的,而Dijkstra算法是针对 有向图 的最短路径生成。一个的目的是连接图中的所有顶点,生成一

    2024年02月03日
    浏览(49)
  • 【数据结构】最短路径算法实现(Dijkstra(迪克斯特拉),FloydWarshall(弗洛伊德) )

    最短路径问题 :从在带权有向图G中的某一顶点出发,找出一条通往另一顶点的最短路径,最短也就是沿路径各边的权值总和达到最小。 单源最短路径问题:给定一个图G = ( V , E ) G=(V,E)G=(V,E),求源结点s ∈ V s∈Vs∈V到图 中每个结点v ∈ V v∈Vv∈V的最短路径 针对一个带权

    2024年02月04日
    浏览(50)
  • 【数据结构与算法】如何对快速排序进行细节优化以及实现非递归版本的快速排序?

    君兮_的个人主页 即使走的再远,也勿忘启程时的初心 C/C++ 游戏开发 Hello,米娜桑们,这里是君兮_,国庆长假结束了,无论是工作还是学习都该回到正轨上来了,从今天开始恢复正常的更新频率,今天为大家带来的内容是快速排序的两大优化和非递归实现 好了废话不多说,开

    2024年02月08日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包