Dijkstra算法

Dijkstra算法

Scroll Down

1、最短路径问题介绍

问题解释:
从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径,称为最短路径

解决问题的算法:

这篇博客,就对Dijkstra算法来做一个详细的整理

1、什么是Dijkstra算法

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。

2、Dijkstra算法介绍

  • 算法特点:
    迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

  • 算法的思路
    Dijkstra算法采用的是一种贪心的策略,声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合:T,初始时,原点 s 的路径权重被赋为 0 (dis[s] = 0)。若对于顶点 s 存在能直接到达的边(s,m),则把dis[m]设为w(s, m),同时把所有其他(s不能直接到达的)顶点的路径长度设为无穷大。初始时,集合T只有顶点s。
    然后,从dis数组选择最小值,则该值就是源点s到该值对应的顶点的最短路径,并且把该点加入到T中,OK,此时完成一个顶点,
    然后,我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短,如果是,那么就替换这些顶点在dis中的值。
    然后,又从dis中找出最小值,重复上述动作,直到T中包含了图的所有顶点。

3、Dijkstra算法示例演示

求下图,从顶点v1到其他各个顶点的最短路径

20170308144724663.png

首先第一步,我们先声明一个dis数组,该数组初始化的值为:

1.png

我们的顶点集T的初始化为:T=

既然是求 v1顶点到其余各个顶点的最短路程,那就先找一个离 1 号顶点最近的顶点。通过数组 dis 可知当前离v1顶点最近是 v3顶点。当选择了 2 号顶点后,dis[2](下标从0开始)的值就已经从“估计值”变为了“确定值”,即 v1顶点到 v3顶点的最短路程就是当前 dis[2]值。将V3加入到T中。
为什么呢?因为目前离 v1顶点最近的是 v3顶点,并且这个图所有的边都是正数,那么肯定不可能通过第三个顶点中转,使得 v1顶点到 v3顶点的路程进一步缩短了。因为 v1顶点到其它顶点的路程肯定没有 v1到 v3顶点短.

OK,既然确定了一个顶点的最短路径,下面我们就要根据这个新入的顶点V3会有出度,发现以v3 为弧尾的有: < v3,v4 >,那么我们看看路径:v1–v3–v4的长度是否比v1–v4短,其实这个已经是很明显的了,因为dis[3]代表的就是v1–v4的长度为无穷大,而v1–v3–v4的长度为:10+50=60,所以更新dis[3]的值,得到如下结果:

2.png

因此 dis[3]要更新为 60。这个过程有个专业术语叫做“松弛”。即 v1顶点到 v4顶点的路程即 dis[3],通过 < v3,v4> 这条边松弛成功。这便是 Dijkstra 算法的主要思想:通过“边”来松弛v1顶点到其余各个顶点的路程。

然后,我们又从除dis[2]和dis[0]外的其他值中寻找最小值,发现dis[4]的值最小,通过之前是解释的原理,可以知道v1到v5的最短距离就是dis[4]的值,然后,我们把v5加入到集合T中,然后,考虑v5的出度是否会影响我们的数组dis的值,v5有两条出度:< v5,v4>和 < v5,v6>,然后我们发现:v1–v5–v4的长度为:50,而dis[3]的值为60,所以我们要更新dis[3]的值.另外,v1-v5-v6的长度为:90,而dis[5]为100,所以我们需要更新dis[5]的值。更新后的dis数组如下图:

3.png

然后,继续从dis中选择未确定的顶点的值中选择一个最小的值,发现dis[3]的值是最小的,所以把v4加入到集合T中,此时集合T={v1,v3,v5,v4},然后,考虑v4的出度是否会影响我们的数组dis的值,v4有一条出度:< v4,v6>,然后我们发现:v1–v5–v4–v6的长度为:60,而dis[5]的值为90,所以我们要更新dis[5]的值,更新后的dis数组如下图:

4.png

然后,我们使用同样原理,分别确定了v6和v2的最短路径,最后dis的数组的值如下:

5.png

因此,从图中,我们可以发现v1-v2的值为:∞,代表没有路径从v1到达v2。所以我们得到的最后的结果为:

起点  终点    最短路径    长度
v1    v2     无          ∞    
      v3     {v1,v3}    10
      v4     {v1,v5,v4}  50
      v5     {v1,v5}    30
      v6     {v1,v5,v4,v6} 60

Dijkstra算法的代码实现(Java)

Dis类

/**
 * 记录起点到每个顶点的最短路径的信息
 */
public class Dis {
    private String path;
    private boolean visit;
    private int value;

    public Dis() {
    }

    public Dis(String path, boolean visit, int value) {
        this.path = path;
        this.visit = visit;
        this.value = value;
    }

    public String getPath() {
        return path;
    }

    public void setPath(String path) {
        this.path = path;
    }

    public boolean isVisit() {
        return visit;
    }

    public void setVisit(boolean visit) {
        this.visit = visit;
    }

    public int getValue() {
        return value;
    }
    
    public void setValue(int value) {
        this.value = value;
    }
}

实现类

/**
 * 实现类
 */
public class Dijkstra {
    private int V;                  //  图的顶点个数
    private int E;                  //  图的边数
    private int[][] graph;          //  图的邻接矩阵
    private Dis[] dis;              //  记录各个顶点最短路径的信息

    /**
     * 构造函数
     * @param V
     * @param E
     */
    public Dijkstra(int V, int E) {
        //初始化顶点数和边数
        this.V = V;
        this.E = E;
        //为邻接矩阵和Dis数组开辟空间及赋初值
        this.graph = new int[V][V];
        this.dis = new Dis[V];
        for (int v = 0; v < V; v++) {
            dis[v] = new Dis();
            for (int i = 0; i < V; i++) {
                graph[v][i] = Integer.MAX_VALUE;
            }
        }
    }

    /**
     * 为邻接矩阵对应点赋值
     * @param from
     * @param to
     * @param weight
     */
    public void addEdge(int from, int to, int weight) {
        graph[from][to] = weight;
        //加上这句就是无向图
        //graph[to][from] = weight;
    }

    /**
     * Dijkstra算法实现
     * @param start
     */
    public void dijkstra(int start) {
        //初始化Dis数组
        for (int i = 0; i < V; i++) {
            //设置当前的路径
            dis[i].setPath("V" + String.valueOf(start) + "->V" + String.valueOf(i));
            dis[i].setValue(graph[start][i]);
        }
        //设置起点到起点的路径为0
        dis[start].setValue(0);
        dis[start].setVisit(true);

        //计算剩余的顶点的最短路径(剩余 V - 1 个顶点)
        for (int v = 1; v < V; v++) {
            //min记录的当前的最小值
            //index用于保存当前dis数组中最小的那个下标
            int min = Integer.MAX_VALUE;
            int index = 0;
            for (int i = 0; i < V; i++) {
                if (!dis[i].isVisit() && dis[i].getValue() < min) {
                    min = dis[i].getValue();
                    index = i;
                }
            }
            //把index对应的顶点标记为已访问过
            dis[index].setVisit(true);
            for (int j = 0; j < V; j++) {
                //如果新得到的边可以影响其他为访问的顶点,那就就更新它的最短路径和长度
                if (!dis[j].isVisit() && graph[index][j] != Integer.MAX_VALUE && (dis[index].getValue() + graph[index][j] < dis[j].getValue())) {
                    dis[j].setPath(dis[index].getPath() + "->V" + String.valueOf(j));
                    dis[j].setValue(graph[index][j] + dis[index].getValue());
                }
            }
        }
    }

    public void printPath() {
        for (int i = 1; i < this.V; i++) {
            if (dis[i].getValue() != Integer.MAX_VALUE) {
                System.out.println(dis[i].getPath() + "\t\t最短路径长度为" + dis[i].getValue());
            } else {
                System.out.println(dis[i].getPath() + "\t\t无最短路径");
            }
        }
    }

    public void printGraph() {
        for (int[] a : graph) {
            for (int i = 0; i < a.length; i++) {
                if (a[i] == Integer.MAX_VALUE) {
                    System.out.print("\tMAX\t");
                } else {
                    System.out.print("\t" + a[i] + "\t");
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();
        int E = sc.nextInt();
        Dijkstra dijkstra = new Dijkstra(V, E);
        for (int i = 0; i < E; i++) {
             dijkstra.addEdge(sc.nextInt(), sc.nextInt(), sc.nextInt());
        }
        dijkstra.dijkstra(0);
        dijkstra.printPath();
    }
}

测试

/**
 * 测试数据
 * 6 11
 * 0 1 50
 * 0 2 10
 * 0 4 45
 * 1 4 10
 * 1 2 15
 * 2 0 20
 * 2 3 15
 * 3 1 20
 * 3 4 35
 * 4 3 30
 * 5 3 3
 * 有向图的邻接矩阵如下:
 *      0       1       2       3       4       5
 * 0    MAX     50      10      MAX     45      MAX
 * 1    MAX     MAX     15      MAX     10      MAX
 * 2    20      MAX     MAX     15      MAX     MAX
 * 3    MAX     20      MAX     MAX     35      MAX
 * 4    MAX     MAX     MAX     30      MAX     MAX
 * 5    MAX     MAX     MAX     3       MAX     MAX
 */

输出

L:\jdk-11.0.2\bin\java.exe "-javaagent:L:\IDEA\IntelliJ IDEA 2018.3.5\lib\idea_rt.jar=54359:L:\IDEA\IntelliJ IDEA 2018.3.5\bin" -Dfile.encoding=UTF-8 -classpath C:\Users\lwj\Desktop\数据结构与算法\out\production\algorithms Main.Graph.Dijkstra
6 11
0 1 50
0 2 10
0 4 45
1 4 10
1 2 15
2 0 20
2 3 15
3 1 20
3 4 35
4 3 30
5 3 3
V0->V2->V3->V1 最短路径长度为45
V0->V2 最短路径长度为10
V0->V2->V3 最短路径长度为25
V0->V4 最短路径长度为45
V0->V5 无最短路径

总结

Dijkstra算法适用于权值为非负的图的单源最短路径,算法时间复杂度为O(n^2)

支付宝 微信