专栏首页bigsai最短路径—弄懂Dijkstra(迪杰斯特拉)算法

最短路径—弄懂Dijkstra(迪杰斯特拉)算法

看前点个关注、蟹蟹

介绍

对于 dijkstra算法,很多人可能感觉熟悉而又陌生,可能大部分人比较了解 bfs和dfs,而对dijkstra和floyd算法可能知道大概是图论中的某个算法,但是可能不清楚其中的作用和原理,又或许,你曾经感觉它很难,那么,这个时候正适合你重新认识它。

Dijkstra能是干啥的?

Dijkstra是用来求单源最短路径的

就拿上图来说,假如知道的路径和长度已知,那么可以使用 dijkstra算法计算南京到图中所有节点的最短距离。

单源什么意思?

  • 从一个顶点出发,Dijkstra算法只能求一个顶点到其他点的最短距离而不能任意两点。

bfs求的最短路径有什么区别?

  • bfs求的与其说是路径,不如说是次数。因为bfs他是按照队列一次一次进行加入相邻的点,而两点之间没有权值或者权值相等(代价相同)。处理的更多是偏向迷宫类的这种都是只能走邻居(不排除特例)。

Dijkstra在处理具体实例的应用还是很多的,因为具体的问题其实带权更多一些。

比如一个城市有多个乡镇,乡镇可能有道路,也可能没有,整个乡镇联通,如果想计算每个乡镇到a镇的最短路径,那么Dijkstra就派上了用场。

算法分析

对于一个算法,首先要理解它的运行流程。对于一个Dijkstra算法而言,前提是它的前提条件和环境:

  • 一个连通图,若干节点,节点可能有数值,但是 路径一定有 权值。并且路径不能为负。否则Dijkstra就不适用。

Dijkstra的核心思想是贪心算法的思想。不懂贪心?

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。

对于贪心算法,在很多情况都能用到。下面举几个不恰当的例子!

打个比方,吃自助餐,目标是吃回本,那么胃有限那么每次都仅最贵的吃。 上学时,麻麻说只能带5个苹果,你想带最多,那么选五个苹果你每次都选最大的那个五次下来你就选的最重的那个。

不难发现上面的 策略虽然没有很强的理论数学依据,或者不太好说明。但是事实规律就是那样,并且对于贪心问题大部分都需要排序,还可能会遇到类排序。并且一个物体可能有多个属性,不同问题需要按照不同属性进行排序,操作。

那么我们的 Dijkstra是如何贪心的呢?对于一个点,求图中所有点的最短路径,如果没有正确的方法胡乱想确实很难算出来,并且如果暴力匹配复杂度呈指数级上升不适合解决实际问题。

那么我们该怎么想呢?

Dijkstra算法的前提

  1. 首先,Dijkstra处理的是带正权值的 有权图,那么,就需要一个二维数组(如果空间大用list数组)存储各个点到达( )的权值大小。(邻接矩阵或者邻接表存储)
  2. 其次,还需要一个boolean数组判断那些点已经确定最短长度,那些点没有确定。int数组记录距离(在算法执行过程可能被多次更新)。
  3. 需要优先队列加入已经确定点的周围点。每次抛出确定最短路径的那个并且确定最短,直到所有点路径确定最短为止。

简单的概括流程为

  • 一般从选定点开始抛入优先队列。(路径一般为0), boolean数组标记0的位置(最短为0) , 然后0 周围连通的点抛入优先队列中(可能是node类),并把各个点的距离记录到对应数组内(如果小于就更新,大于就不动,初始第一次是无穷肯定会更新),第一次就结束了
  • 从队列中抛出 距离最近的那个点 B第一次就是0周围邻居)。这个点距离一定是最近的(所有权值都是正的,点的距离只能越来越长。)标记这个点为 true并且将这个点的邻居加入队列(下一次确定的最短点在前面未确定和这个点邻居中产生),并更新通过 B点计算各个位置的长度,如果小于则更新!
  • 重复二的操作,直到所有点都确定。

算法实现

package 图论;

import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class dijkstra {
    static class node
    {
        int x; //节点编号
        int lenth;//长度
        public node(int x,int lenth) {
            this.x=x;
            this.lenth=lenth;
        }
    }

    public static void main(String[] args) {

        int[][] map = new int[6][6];//记录权值,顺便记录链接情况,可以考虑附加邻接表
        initmap(map);//初始化
        boolean bool[]=new boolean[6];//判断是否已经确定
        int len[]=new int[6];//长度
        for(int i=0;i<6;i++)
        {
            len[i]=Integer.MAX_VALUE;
        }
        Queue<node>q1=new PriorityQueue<node>(com);
        len[0]=0;//从0这个点开始
        q1.add(new node(0, 0));
        int count=0;//计算执行了几次dijkstra
        while (!q1.isEmpty()) {
            node t1=q1.poll();
            int index=t1.x;//节点编号
            int length=t1.lenth;//节点当前点距离
            bool[index]=true;//抛出的点确定
            count++;//其实执行了6次就可以确定就不需要继续执行了  这句可有可无,有了减少计算次数
            for(int i=0;i<map[index].length;i++)
            {
                if(map[index][i]>0&&!bool[i])
                {
                    node node=new node(i, length+map[index][i]);
                    if(len[i]>node.lenth)//需要更新节点的时候更新节点并加入队列
                    {
                        len[i]=node.lenth;
                        q1.add(node);
                    }
                }
            }
        }       
        for(int i=0;i<6;i++)
        {
            System.out.println(len[i]);
        }
    }
    static Comparator<node>com=new Comparator<node>() {

        public int compare(node o1, node o2) {
            return o1.lenth-o2.lenth;
        }
    };

    private static void initmap(int[][] map) {
        map[0][1]=2;map[0][2]=3;map[0][3]=6;
        map[1][0]=2;map[1][4]=4;map[1][5]=6;
        map[2][0]=3;map[2][3]=2;
        map[3][0]=6;map[3][2]=2;map[3][4]=1;map[3][5]=3;
        map[4][1]=4;map[4][3]=1;
        map[5][1]=6;map[5][3]=3;    
    }
}
文章分享自微信公众号:
bigsai

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!

如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 算法:最短路径之迪杰斯特拉(Dijkstra)算法

    对于网图来说,最短路径,是指两顶点之间经过的边上权值之和最少的路径,并且我们称路径上的第一个顶点为源点,最后一个顶点为终点。最短路径的算法主要有迪杰斯特拉(Di...

    s1mba
  • 最短路径问题--迪杰斯特拉(Dijkstra)算法

    迪杰斯特拉(Dijkstra)算法是典型的用来解决最短路径的算法,也是很多教程中的范例,由荷兰计算机科学家狄克斯特拉于1959年提出,用来求从起始点到其他所有点...

    用户6021899
  • 迪杰斯特拉(Dijkstra)算法求图中最短路径

    迪杰斯特拉(Dijkstra )算法: 对于图G=(V,E),将图的顶点分为两组: 顶点集S:已求出的最短路径的顶点集合(初始为{v0}); 顶...

    Steve Wang
  • 最短路径-----迪杰特斯拉算法

    大忽悠爱学习
  • 迪杰斯特拉算法(最短路径问题)

    假如有七个村庄(ABCDEFG),有个人从G点出发,到其他六个村庄的最短路径分别是多少?到A、B、F、E只有一条路,没得选,但是到C有两条路,可以是2 + 7,...

    贪挽懒月
  • 最短路径算法(上)——迪杰斯特拉(Dijikstra)算法

    对于迪杰斯特拉算法的分支界限法解法请移步:利用分支界限法求解Dijikstra算法

    AI那点小事
  • 数据结构与算法-求最短路径之迪杰斯特拉(Dijkstra)算法

    迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径,它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩...

    越陌度阡
  • 单源最短路径之迪杰斯特拉算法

    迪杰斯特拉(Dijkstra)算法解决最短路径问题,其创造者:艾兹格·W·迪科斯彻 (Edsger Wybe Dijkstra)。

    每天学Java
  • C++迪杰斯特拉最短路径算法实现

    input 第一行表示这个图有4条边,下面五行代表这个图的5条边。 4 0 2 2 0 1 5 1 3 2 2 3 6 -1 0 0 ? 输入样例 out 分别...

    kalifa_lau
  • ACM算法竞赛——堆优化版dijkstra(模板)

    战士小小白
  • 一步一步深入理解Dijkstra算法

    先简单介绍一下最短路径: 最短路径是啥?就是一个带边值的图中从某一个顶点到另外一个顶点的最短路径。 官方定义:对于内网图而言,最短路径是指两顶点之间经过的边...

    Angel_Kitty
  • 迪杰斯特拉算法(Dijkstra)算法

    2.执行上述 4、5两步骤,找出U集合中路径最短的节点D 加入S集合,并根据条件 if ( 'D 到 B,C,E 的距离' + 'AD 距离' < 'A 到 B...

    狼啸风云
  • [图]最短路径-Dijkstra算法

    2.BFS可能会是Dijkstra算法的实质,BFS使用的是队列进行操作,而Dijkstra采用的是优先队列。

    王荣胜
  • 【你该懂一点Javascript算法系列】之单源最短路径 - Dijkstra算法

    ps: 邻接矩阵的意思是: 用一个二数组表示个顶点间的关系,来确定各顶点间的关系,因为图为有向图,所以上图的邻接矩阵如上

    super.x
  • 迪杰斯特拉算法原理Dijkstra

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

    里克贝斯
  • 迪杰斯特拉(dijkstra)c语言实现方法

    迪杰斯特拉(dijkstra)是用来实现查找一个点到其它点最短路径的一种方法。通过查找从起点到最短距离的点,然后将该点放入到集合中,代表以及找到起点到这一点的最...

    诸葛青云
  • 最短路问题

    过去我也有美梦来着,有幻想来着,可不知神魔时候,都烟消云散了,还是遇见你之前的事。

    AngelNH
  • 图论--差分约束系统

    求x1-x4的最大值,由题目给的式子1,2,4可得x1-x4>=11,我们来看图中最短路,x1到X4的最短距离也是11,也就是说差分约束系统就是将给定条件转化为...

    风骨散人Chiam
  • 最短路径-Dijkstra算法

    Dijkstra算法,又称"迪杰斯特拉算法",是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层...

    仙士可

扫码关注云+社区

领取腾讯云代金券