精华内容
下载资源
问答
  • 前言在图论中,在寻路最短路径中除了Dijkstra算法以外,还有Floyd算法也是非常经典,然而算法还是有区别的,Floyd主要计算多源最短路径。在单源正权值最短路径,我们会用Dijkstra算法来求最短路径,并且算法的...

    前言

    920357dec1fc61363356abacc4eee3ed.png

    图论中,在寻路最短路径中除了Dijkstra算法以外,还有Floyd算法也是非常经典,然而两种算法还是有区别的,Floyd主要计算多源最短路径。

    在单源正权值最短路径,我们会用Dijkstra算法来求最短路径,并且算法的思想很简单——贪心算法:每次确定最短路径的一个点然后维护(更新)这个点周围点的距离加入预选队列,等待下一次的抛出确定。但是虽然思想很简单,实现起来是非常复杂的,我们需要邻接矩阵(表)储存长度,需要优先队列(或者每次都比较)维护一个预选点的集合。还要用一个boolean数组标记是否已经确定、还要---------

    总之,Dijkstra算法的思想上是很容易接受的,但是实现上其实是非常麻烦的。但是单源最短路径没有更好的办法。复杂度也为O(n2)

    而在n节点多源最短路径中,如果从Dijkstra算法的角度上,只需要将Dijkstra封装,然后执行n次Dijkstra算法即可,复杂度为O(n3)。但是这样感觉很臃肿,代码量巨大,占用很多空间内存。有没有啥方法能够稍微变变口味呢?

    答案是有的,这就是易写但稍需要理解的Floyd算法。一个求多元最短路径算法。

    算法介绍

    先看看百度百科的定义吧:

    Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

    简单的来说,算法的主要思想是动态规划(dp),而求最短路径需要不断松弛(熟悉spfa算法的可能熟悉松弛)。

    而算法的具体思想为:

    1. 邻接矩阵dist储存路径,同时最终状态代表点点的最短路径。如果没有直接相连的两点那么默认为一个很大的值(不要溢出)!而自己的长度为0.

    2. 第1个到第n个点依次加入图中。每个点加入进行试探是否有路径长度被更改,这个长度就是说两点距离会不会因为新加入的点变得更短(a_k_b距离

    3. 而上述试探具体方法为遍历图中每一个点(i,j双重循环),判断每一个点对距离是否因为加入的点而发生最小距离变化。如果发生改变,那么两点(i,j)距离就更改。

    4. 重复上述直到最后插点试探完成。

    其中第三步的状态转移方程为:

    • dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
      其中dp[x][y]的意思可以理解为x到y的最短路径。所以dp[i][k]的意思可以理解为i到k的最短路径dp[k][j]的意思可以理解为k到j的最短路径.

    咱们图解一个案例:

    609b858da8c10d305ec3109697af232d.png
    在这里插入图片描述

    默认的最短长度初始为邻接矩阵初始状态

    • 加入第一个节点1,大家可以发现,由于1的加入,使得本来不连通的2,3点对和2,4点对变得联通,并且加入1后距离为当前最小。(可以很直观加入5之后2,4,更短但是还没加入)。为了更好的描述其实此时的直接联通点多了两条。(2,3)和(2,4).我们在dp中不管这个结果是通过前面那些步骤来的,但是在这个状态,这两点的最短距离就算它!

      8922baa615b547dbc94fa16957dce653.png
      在这里插入图片描述
    • 同时你可以发现加入1其中也使得3,1,4这样联通,但是 3,1,4联通的话距离为9远远大于本来的(3,4)为2,所以不进行更新。

    • 咱们继续加入第二个节点。在加入的初始态为:

      0f0c6b4ecb62d4c83040afcffe76fe26.png
      在这里插入图片描述
    • 进行遍历插入看看是否更新节点

      0a5b7a611e536401486ad2d504664ff7.png
      在这里插入图片描述


      实际上这个时候图中的连线就比较多了。当然这些连线都是代表当前的最短路径。 这也和我们的需求贴合,我们最终要的是所有节点的最短路径。每个节点最终都应该有6条指向不同节点的边! 表示邻接矩阵的最终结果。

    至于算法的模拟两部核心已经告诉大家了,大家可以自行模拟剩下的。

    程序实现

    而对于程序而言,这个插入的过程相当简单。核心代码只有四行
    代码如下

    public class floyd {
        static int max = 66666;// 别Intege.max 两个相加越界为负
        public static void main(String[] args) {
            int dist[][] = {
                    { 0236, max, max }, 
                    { 20, max,max, 46 }, 
                    { 3, max, 02, max, max },
                    { 6, max, 2013 }, 
                    { max, 4, max, 10, max }, 
                    { max, 6, max, 3, max, 0 } };// 地图
            // 6个
            for (int k = 0; k 6; k++)// 加入滴k个节点
            {
                for (int i = 0; i 6; i++)// 松弛I行
                {
                    for (int j = 0; j 6; j++)// 松弛i列
                    {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
            // 输出
            for (int i = 0; i 6; i++) {
                System.out.print("节点"+(i+1)+" 的最短路径");
                for (int j = 0; j 6; j++) {
                    System.out.print(dist[i][j]+" ");
                }
                System.out.println();
            }
        }
    }

    结果为:

    7ecbf8def9b781f4396506cbac51a6ee.png

    可以自行计算,图和上篇的Dijkstra是一致的,大家可以自行比对,结果一致,说明咱么的结果成功的。

    当然,在你学习的过程中,可以在每加入一个节点插入完成后,打印邻接矩阵的结果,看看前两部和笔者的是否相同(有助于理解),如果相同,则说明正确!

    你可能还会有疑惑,那咱么就用一个局部性来演示一下,看其中AB最短距离变化情况祝你理解:

    a85c6a9c6c99f6dc1082c94c4566f6ab.png
    在这里插入图片描述

    好啦,Floyd算法就介绍到这里,如果对你有帮助,请动动小手点个赞吧!蟹蟹。

    推荐阅读:数据结构能干吗,我花了一夜给女朋友写个走迷宫游戏最短路径—弄懂Dijkstra(迪杰斯特拉)算法一种非大小排序(先后关系排序)—拓扑排序数据结构与算法—深度、宽度优先(dfs,bfs)搜索哈夫曼树(最优二叉树)详解与构造写文没高质量配图?教你python爬虫绕过限制一键搜索下载图虫创意图片!一文搞懂简单数据结构—并查集(不相交集合)从阶乘、斐波那契、汉诺塔剖析彻底搞懂递归算法

    希望和各位共同进步!欢迎关注笔者公众号:bigsai

    b1116b249efa50cfe5c6398835551cbd.png

    展开全文
  • 任务描述:在一个无向图中,获取起始节点到所有其他节点的最短路径描述Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始为中心向外层层扩展,直到...

    任务描述:在一个无向图中,获取起始节点到所有其他节点的最短路径描述

    Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。

    Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表方式

    用OPEN,CLOSE表的方式,其采用的是贪心法的算法策略,大概过程如下:

    1.声明两个集合,open和close,open用于存储未遍历的节点,close用来存储已遍历的节点

    2.初始阶段,将初始节点放入close,其他所有节点放入open

    3.以初始节点为中心向外一层层遍历,获取离指定节点最近的子节点放入close并从新计算路径,直至close包含所有子节点

    代码实例如下:

    Node对象用于封装节点信息,包括名字和子节点

    public class Node {

    private String name;

    private Map child=new HashMap();

    public Node(String name){

    this.name=name;

    }

    public String getName() {

    return name;

    }

    public void setName(String name) {

    this.name = name;

    }

    public Map getChild() {

    return child;

    }

    public void setChild(Map child) {

    this.child = child;

    }

    }

    MapBuilder用于初始化数据源,返回图的起始节点

    public class MapBuilder {

    public Node build(Set open, Set close){

    Node nodeA=new Node("A");

    Node nodeB=new Node("B");

    Node nodeC=new Node("C");

    Node nodeD=new Node("D");

    Node nodeE=new Node("E");

    Node nodeF=new Node("F");

    Node nodeG=new Node("G");

    Node nodeH=new Node("H");

    nodeA.getChild().put(nodeB, 1);

    nodeA.getChild().put(nodeC, 1);

    nodeA.getChild().put(nodeD, 4);

    nodeA.getChild().put(nodeG, 5);

    nodeA.getChild().put(nodeF, 2);

    nodeB.getChild().put(nodeA, 1);

    nodeB.getChild().put(nodeF, 2);

    nodeB.getChild().put(nodeH, 4);

    nodeC.getChild().put(nodeA, 1);

    nodeC.getChild().put(nodeG, 3);

    nodeD.getChild().put(nodeA, 4);

    nodeD.getChild().put(nodeE, 1);

    nodeE.getChild().put(nodeD, 1);

    nodeE.getChild().put(nodeF, 1);

    nodeF.getChild().put(nodeE, 1);

    nodeF.getChild().put(nodeB, 2);

    nodeF.getChild().put(nodeA, 2);

    nodeG.getChild().put(nodeC, 3);

    nodeG.getChild().put(nodeA, 5);

    nodeG.getChild().put(nodeH, 1);

    nodeH.getChild().put(nodeB, 4);

    nodeH.getChild().put(nodeG, 1);

    open.add(nodeB);

    open.add(nodeC);

    open.add(nodeD);

    open.add(nodeE);

    open.add(nodeF);

    open.add(nodeG);

    open.add(nodeH);

    close.add(nodeA);

    return nodeA;

    }

    }

    图的结构如下图所示:

    aec0770c4fa0caff092ff3181a25787b.png

    Dijkstra对象用于计算起始节点到所有其他节点的最短路径

    public class Dijkstra {

    Set open=new HashSet();

    Set close=new HashSet();

    Map path=new HashMap();//封装路径距离

    Map pathInfo=new HashMap();//封装路径信息

    public Node init(){

    //初始路径,因没有A->E这条路径,所以path(E)设置为Integer.MAX_VALUE

    path.put("B", 1);

    pathInfo.put("B", "A->B");

    path.put("C", 1);

    pathInfo.put("C", "A->C");

    path.put("D", 4);

    pathInfo.put("D", "A->D");

    path.put("E", Integer.MAX_VALUE);

    pathInfo.put("E", "A");

    path.put("F", 2);

    pathInfo.put("F", "A->F");

    path.put("G", 5);

    pathInfo.put("G", "A->G");

    path.put("H", Integer.MAX_VALUE);

    pathInfo.put("H", "A");

    //将初始节点放入close,其他节点放入open

    Node start=new MapBuilder().build(open,close);

    return start;

    }

    public void computePath(Node start){

    Node nearest=getShortestPath(start);//取距离start节点最近的子节点,放入close

    if(nearest==null){

    return;

    }

    close.add(nearest);

    open.remove(nearest);

    Map childs=nearest.getChild();

    for(Node child:childs.keySet()){

    if(open.contains(child)){//如果子节点在open中

    Integer newCompute=path.get(nearest.getName())+childs.get(child);

    if(path.get(child.getName())>newCompute){//之前设置的距离大于新计算出来的距离

    path.put(child.getName(), newCompute);

    pathInfo.put(child.getName(), pathInfo.get(nearest.getName())+"->"+child.getName());

    }

    }

    }

    computePath(start);//重复执行自己,确保所有子节点被遍历

    computePath(nearest);//向外一层层递归,直至所有顶点被遍历

    }

    public void printPathInfo(){

    Set> pathInfos=pathInfo.entrySet();

    for(Map.Entry pathInfo:pathInfos){

    System.out.println(pathInfo.getKey()+":"+pathInfo.getValue());

    }

    }

    /**

    * 获取与node最近的子节点

    */

    private Node getShortestPath(Node node){

    Node res=null;

    int minDis=Integer.MAX_VALUE;

    Map childs=node.getChild();

    for(Node child:childs.keySet()){

    if(open.contains(child)){

    int distance=childs.get(child);

    if(distance

    minDis=distance;

    res=child;

    }

    }

    }

    return res;

    }

    }

    Main用于测试Dijkstra对象

    public class Main {

    public static void main(String[] args) {

    Dijkstra test=new Dijkstra();

    Node start=test.init();

    test.computePath(start);

    test.printPathInfo();

    }

    }

    打印输出如下:

    D:A->D

    E:A->F->E

    F:A->F

    G:A->C->G

    B:A->B

    C:A->C

    H:A->B->H

    以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。

    展开全文
  • 单源最短路径算法Dijkstra算法解决的问题算法的思想Java代码实现 算法解决的问题 在图中寻找从一个到其他的最短路径问题,例如,外卖小哥从店里出发,到其他各个买家的最短路径是多少 算法的思想 该算法使用贪心...

    算法解决的问题

    在图中寻找从一个点到其他点的最短路径问题,例如,外卖小哥从店里出发,到其他各个买家的最短路径是多少

    算法的思想

    该算法使用贪心的思想,具有两个阈,一个是S阈(表示已经加入的点,初始只有起点),一个是U阈,表示还没有加入的。
    首先有个dis数组,记录的是从起点到达其他点的最短路径,然后选择最短的那个,加入到S中去。然后由于新点的加入,更新dis数组,直到所有的点都加入S中为止。

    Java代码实现

    private static void dijkstra(int[][] graph, int[] dis, boolean[] visited) {
            while (true){
                int min = Integer.MAX_VALUE;
                int index=-1;
                for(int i=0;i<dis.length;i++){
                    if(visited[i]){
                        continue;
                    }else{
                        if(min>dis[i]) {
                            min = Math.min(min, dis[i]);
                            index = i;
                        }
                    }
                }
                if(index==-1){//说明所有的点都加入S中,结束
                    break;
                }
                visited[index]=true;//加入到S中
                for(int i=0;i<graph[0].length;i++){//更新dis
                    if(graph[index][i]!=Integer.MAX_VALUE){
                        dis[i]=Math.min(dis[i],min+graph[index][i]);
                    }
                }
            }
        }
    
    展开全文
  • Djkstra算法是求解单源(起始固定)最短路径问题的一种经典方法,它采用了贪心策略(其实我觉得也是动态规划),可以求得图中的一个到其他所有的距离,计算复杂度是 O(E|V|),如果采用最小堆优化可以达到O(ElogV )...

    Djkstra算法是求解单源(起始点固定)最短路径问题的一种经典方法,它采用了贪心策略(其实我觉得也是动态规划),可以求得图中的一个点到其他所有点的距离,计算复杂度是 O(E|V|),如果采用最小堆优化可以达到O(ElogV )。算法的整体思想是将顶点分成两类:已经构成最短路的点的集合V1和没有构成最短路的点的集合V2。我们将dist[i]设置为第 i个点到V1的距离,每次将V2中取距离V1集合最短的点P放入V1中,同时因为P被放入了V1,那么其他点到V1的最短路就有可能通过P了,所以我们更新所有集合V2内的点j到V1的距离dist[j] = min( dist[j], dist[i_P] + G[i_P][j] ),其中i_P表示P的下标, G[i_P][j] 表示图中P到j的距离。但是需要注意一点:Djkstra算法不能解决具有负权边的最短路径问题。显然,当具有负权边的时候你无法保证每次放入V1的都是最短路径, 具体可以参考点击打开链接,讲的很清楚。我们以下图为例编写代码,图的左边是最短路的真实结果,右边是图

    ae716316532b65cce4f6e62c4459e66a.png
    #include #include#includeusing namespace std; #define MAX_PATH 999999 int shortestId( const vector& dist, const vector& isShortest ) //寻找当前未放入最短路径集合的所有ID中路径最短的ID号{ int min_dist = MAX_PATH; int min_ID = -1; for(int i = 0; i < dist.size() ; i++) { if(false == isShortest[i]){ if(dist[i] < min_dist){ min_dist = dist[i]; min_ID = i; } } } return min_ID;}vector Djkstra( const vector >& Graph){ int num_vertex = Graph.size(); vector isShortest( num_vertex, false); //初始化只有第一个顶点(index = 0)被放入最短路的ID集合中 isShortest[0] = true; vector dist(num_vertex, MAX_PATH); //dist[i]表示当前节点 i+1(下标i)到最短路的id集合中所有点的最短距离 dist[0] = 0;  for(int i = 1 ;i < num_vertex; i++) { if(Graph[0][i]  >& Graph){ Graph[startP][endP] = weight; //Graph[endP][startP] = weight;} int main(){ vector > Graph(6, vector(6, MAX_PATH) ); addEdge(0,1,10 ,Graph); addEdge(0,5,3 ,Graph); addEdge(1,2,7 ,Graph); addEdge(1,3,5 ,Graph); addEdge(3,0,3,Graph); addEdge(3,2,4,Graph); addEdge(3,4,7,Graph); addEdge(5,1,2,Graph); addEdge(5,3,6,Graph); addEdge(5,4,1,Graph); /* for(int i =0 ; i < Graph.size(); i++) { for(int j = 0; j < Graph.size(); j++) cout << Graph[i][j] << ""; cout < shortestDist = Djkstra(Graph); for(int i = 0; i 

    最后,如果你想学C/C++可以私信小编“01”获取素材资料以及开发工具和听课权限哦!

    展开全文
  • 地理信息系统原理课件 地理信息系统基础本书结构 第一章 绪论 第二章 地理信息系统的构成 第三章 空间数据获取 第四章 空间数据的表达 第五章 空间数据的处理 第六章 空间数据的管理 第七章 空间查询与空间分析 第八...
  • 最短路径算法

    2021-01-03 01:01:44
    最短路径算法:Dijkstra和Bellman Dijkstra 问题:在一张图中,从一点出发到大其他个的最短路径。 思路:假设a到b之前的直达路径是10,如果求a到b的最短路径,就需要抄近路,比如加个c,a->c->b,看这...
  • Dijkstra最短路径树 VS Prim最小生成树 具象表现为: 1)二者都是通过添加边负的方式构造树 2)prim算法每一步添加的是离树最近的非树顶点 ...若想要实现任意两点最短路径,只需要把图中的所有顶点
  • 算法思想:将各收费站及其...基于以上分析:车辆从任意A进站从任意B出站的收费问题就演化成求加权图中任意两点最短路径的问题(前提:过路费按最短路径收取),采用floyd算法很容易实现求任意两点最短路径的问题
  • 图的最短路径算法

    2020-09-08 13:57:19
    最短路径算法 Dijkstra最短路径算法 Floyd最短路径算法 Flody算法可以求图中任意两点的最短路径,边权可以为负,但是不可以有负环。 #include <cstdio> using namespace std; const int MAXN = 30; const ...
  • 本文主要讲述最短路径算法,一个主要原因是网上的“基于Matlab实现的两点之间最短路径算法”存在各种实现错误,目前为止还没有找到一个完全正确的。所以,本人改正相关错误,上传个正确的版本,即:采用Matlab实现的...
  • 是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始为中心向外层层扩展,直到扩展到终点为止。 Ø 基本思想 ​ 通过Dijkstra计算图G中的最短路径时,需要...
  • 最短路径算法Dijkstra

    2020-08-27 15:41:07
    而地杰斯特拉算法和弗洛伊德算法是为了解决任意两点之间的最短路径问题,就好比送快递路线选择问题,打开手机地图输入目的地给你规划出来的路线方案,这就是求单点最短路径问题。 Dijkstra 该算法采用的思想有点类似...
  • 最短路径算法1.Dijkstra算法2.Bellman-Ford算法3.SPFA算法4.Floyd算法几种最短路径算法的对比Dijkstra算法、Bellman-Ford算法和SPFA算法的对比Dijkstra算法和Floyd算法的对比 最短路径算法 单源最短路算法:已知...
  • 9.4 最短路径算法

    2021-02-16 17:28:10
    最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中结点之间的最短路径算法具体的形式包括: 确定起点的最短路径问题 - 即已知起始结点,求起始到所有最短路径的问题。 ...
  • 并行最短路径算法Dijkstra。 为实现并行最短路径计算,我们必须要解决如下问题: (1)数据获取:利用随机函数生成大约2000个节点及其节点之间的距离。本程序使用邻接矩阵来存储带权有向图的信息。矩阵大小2000*2000...
  • 这种题目在图里面也不算非常常见 但是一旦见到 这算法就很明显 所以看到这种题目就应该立刻想到最短路径算法 然后需要立刻定位到自己需要用的那种算法。不然虽然知道最短路径算法 但是不知道要选择哪个 就会十分慌乱...
  • Dijkstra最短路径算法

    2017-10-27 18:03:11
    Dijkstra最短路径算法是一种单源最短路径算法,该算法要求路径上任意两点间路径为非负权边。用于计算从路径中指定的顶点到其他所有的顶点的最短路径。所以广泛应用于能够建模为图的问题中,用以查找两个节点最短路径...
  • 最短路径算法——Floyd算法 Floyd算法是以它的创始人之一斯坦福大学计算机科学系的罗伯特·弗洛伊德教授名字命名的一种算法。它是一种利用动态规划的思想寻找给定的加权图中多源之间最短路径的算法,采用带权邻接...
  • 前言在图论中,在寻路最短路径中除了Dijkstra算法以外,还有Floyd算法也是非常经典,然而算法还是有区别的,Floyd主要计算多源最短路径。在单源正权值最短路径,我们会用Dijkstra算法来求最短路径,并且算法的...
  • matlab 最短路径算法

    2015-06-09 09:46:29
    两点最短路径,已经最短路径经过的其他节点情况
  • 最短路径算法floyd

    2019-07-03 16:00:06
    floyd最短路径算法是用于求图中任意两点之间最短路径的经典算法,但是绝大多数的讲解只是用三个循环简单带过。今天在学习spfa算法时有感得出其 可能 的内在逻辑。 图内有A,B点,以及N个点(包含A,B)。A到B的边数...
  • Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始为中心向外层层扩展,直到扩展到终点为止。Dijkstra一般的表述通常有种方式,一种用永久和临时...
  • 一个物流方面的需求, 通过两点...想问下 这个需求该如何入手呢 在网上没找到同时满足 有向 任意两点 这两个条件的最短路径算法; [img=https://img-bbs.csdn.net/upload/201506/29/1435570969_829639.jpg][/img]
  • acm-最短路径算法

    2019-05-22 23:31:54
    最短路径算法 ...简称Floyed(弗洛伊德)算法,是最简单的最短路径算法,可以计算图中任意两点间的最短路径。Floyed的时间复杂度是O (N3),适用于出现负边权的情况。 算法描述: 初始化:点u、v如...
  • 一心想学习算法,很少去真正静下心来去研究,前几天趁着周末去了解了最短路径的资料,用python写了一个最短路径算法。算法是基于带权无向图去寻找之间的最短路径,数据存储用邻接矩阵记录。首先画出一幅无向图...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,043
精华内容 1,217
关键字:

两点最短路径算法