问题定义

求解单元点的最短路径问题：给定带权有向图G和源点v，求v到G中其他顶点的最短路径

限制条件：图G中不存在负权值的边（这个可以通过弗洛伊德算法，后期将进行讲解）

核心思想

设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。

在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。

此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

最短路径的证明

（反证法可证）

求最短路径步骤

算法步骤如下：

G={V,E}

1、 初始时令 S={V0},T=V-S={其余顶点}，T中顶点对应的距离值

若存在 <V0,Vi>，d(V0,Vi)为 <V0,Vi> 弧上的权值

若不存在 <V0,Vi>，d(V0,Vi) 为 ∞

2、从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中

3、对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值重复上述步骤2、3，直到S中包含峙所有顶点，即W=Vi为止

算法

迪克斯特拉算法

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于 1959 年提出的，因此又叫狄克斯特拉算法。

是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。

迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

定义

Dijkstra算法一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。

注意该算法要求图中不存在负权边。

动态图

2012073019540660

ps: 动态图仅仅提供直观性，思考的时候不建议参考这个图。

算法流程

大概就是这样一个有权图，Dijkstra 算法可以计算任意节点到其他节点的最短路径

image

算法思路

1、指定一个节点，例如我们要计算 ‘A’ 到其他节点的最短路径

2、引入两个集合（S、U），S集合包含已求出的最短路径的点（以及相应的最短长度），U集合包含未求出最短路径的点（以及A到该点的路径，注意 如上图所示，A->C由于没有直接相连 初始时为∞）

3、初始化两个集合，S集合初始时 只有当前要计算的节点，A->A = 0，

U集合初始时为 A->B = 4, A->C = ∞, A->D = 2, A->E = ∞

ps: 直接连接的定义长度，其他认为不可达。

接下来要进行核心两步骤了

4、从U集合中找出路径最短的点，加入S集合，例如 A->D = 2

ps: 这里就是一个核心的排序流程，选择最近的一个点加入集合。

5、更新U集合路径，if ( ‘D 到 B,C,E 的距离’ + ‘AD 距离’ < ‘A 到 B,C,E 的距离’ ) 则更新U

ps: 如果通过新的路径可以让距离变得更短，就更新集合 U 信息。

6、循环执行 4、5 两步骤，直至遍历结束，得到A 到其他节点的最短路径

算法图解

1、选定A节点并初始化，如上述步骤3所示

image

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

image

3、这时候 A->B, A->C 都为3，没关系。其实这时候他俩都是最短距离，如果从算法逻辑来讲的话，会先取到B点。

而这个时候 if 条件变成了 if ( ‘B 到 C,E 的距离’ + ‘AB 距离’ < ‘A 到 C,E 的距离’ ) ，如图所示这时候A->B距离，其实为 A->D->B

image

4、思路就是这样，往后就是大同小异了

image

5、算法结束

image

实际例子

下面是另外一个例子，可以跳过。

无向图

image

流程

用Dijkstra算法找出以A为起点的单源最短路径步骤如下

image

理解

  [plaintext]
1
2
3
按最短路径长度的递增次序依次把第二组的顶点加入S中。

在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度”

迪杰斯特拉算法的运行过程是一个排序的过程，既不是深度优先也不是广度优先算法。

就上面的例子来说，是根据A到图中其余点的最短路径长度进行排序，路径越短越先被找到，路径越长越靠后才能被找到，要找A到F的最短路径，我们依次找到了

  [plaintext]
1
2
3
4
5
A –> C 的最短路径 3
A –> C –> B 的最短路径 5
A –> C –> D 的最短路径 6
A –> C –> E 的最短路径 7
A –> C –> D –> F 的最短路径 9

Dijkstra 算法运行的附加效果是得到了另一个信息，A到C的路径最短，其次是A到B, A到D, A到E, A到F

为什么 Dijkstra 算法不适用于带负权的图？

就上个例子来说，当把一个点选入集合S时，就意味着已经找到了从A到这个点的最短路径，比如第二步，把C点选入集合S，这时已经找到A到C的最短路径了，但是如果图中存在负权边，就不能再这样说了。

举个例子，假设有一个点Z，Z只与A和C有连接，从A到Z的权为50，从Z到C的权为-49，现在A到C的最短路径显然是 A –> Z –> C

ps: 直白地说，负权重会打乱排序。

对带负权的图，应该用 Floyd 算法

语言实现

直观的实现

先用邻接矩阵存储数据，考虑采用一个二重循环，每次寻找出距离集合最近的一个点，然后数组标记它已经加入集合，然后在用当前点对不在集合中的点进行松弛，进行 n^2 次，整个操作就完成了（此处代码中默认起点是1）

  [cpp]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void dijkstra()
{
    memset(dis,127/3,sizeof(dis));//初始化
    v[1]=1;
    dis[1]=0;

    for(int i=1;i<=n;++i)
    {
        int k=0;
        
        for(int j=1;j<=n;++j)//找出距离最近的点
            if(!v[j]&&(k==0||dis[j]<dis[k]))
                k=j;
        v[k]=1;//加入集合

        for(int j=1;j<=n;++j)//松弛
            if(!v[j]&&dis[k]+a[k][j]<dis[j])
                dis[j]=dis[k]+a[k][j];
    }
}

个人 java 实现

有了上面的实现之后，我们来看一下 java 的实现方式。

  [java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import com.github.houbb.data.struct.core.util.graph.shortestpath.IShortestPath;

/**
 * 迪杰斯特拉算法
 * @author binbin.hou
 * @since 0.0.3
 */
public class DijkstraShortestPath implements IShortestPath {

    @Override
    public int[] shortestPath(int[][] graph, int start) {
        // 数组构建
        final int length = graph.length;
        int[] shortestPathArray = new int[length];
        int[] visitedArray = new int[length];

        // 初始化
        // start==>start 路径长度为0
        shortestPathArray[start] = 0;
        // start 节点默认放在集合中
        visitedArray[start] = 1;

        // 开始循环处理剩下的节点
        for(int i = 1; i < length; i++) {
            // 距离 start 最近的点
            int k = -1;
            // 距离 start 最近的距离
            int disMin = Integer.MAX_VALUE;

            //1. 选取出距离顶点 start 最近的一个顶点
            for(int j = 1; j < length; j++) {
                // 元素不在已访问的列表中且
                if(visitedArray[j] == 0 && graph[start][j] < disMin) {
                    disMin = graph[start][j];
                    k = j;
                }
            }

            // 更新信息,加入到最短的集合
            visitedArray[k] = 1;
            shortestPathArray[k] = disMin;

            // 更新距离表
            for(int index = 1; index < length; index++) {
                //1. 不在最短列表中
                //2. start==>shortestIndex+si==>index < start==>index，则进行距离表更新
                if(visitedArray[index] == 0
                    && graph[start][k]+graph[k][index] < graph[start][index]) {
                    graph[start][index] = graph[start][k]+graph[k][index];
                }
            }
        }

        return shortestPathArray;
    }

}

测试代码

  [java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void shortestPathTest() {
    final int M = 10000; // 代表正无穷
    // 二维数组每一行分别是 A、B、C、D、E 各点到其余点的距离,
    // A -> A 距离为0, 常量M 为正无穷
    int[][] graph = {
            {0, 4, M, 2, M},
            {4, 0, 4, 1, M},
            {M, 4, 0, 1, 3},
            {2, 1, 1, 0, 7},
            {M, M, 3, 7, 0}
    };
    int start = 0;
    IShortestPath shortestPath = new DijkstraShortestPath();
    int[] shortPath = shortestPath.shortestPath(graph, start);
    for (int i = 0; i < shortPath.length; i++) {
        System.out.println("从" + start + "出发到" + i + "的最短距离为：" + shortPath[i]);
    }
}
  • 日志输出
  [plaintext]
1
2
3
4
5
从0出发到0的最短距离为：0
从0出发到1的最短距离为：3
从0出发到2的最短距离为：3
从0出发到3的最短距离为：2
从0出发到4的最短距离为：6

堆优化

思考

该算法复杂度为n^2,我们可以发现，如果边数远小于n^2,对此可以考虑用堆这种数据结构进行优化，取出最短路径的复杂度降为O(1)；

每次调整的复杂度降为O（elogn）；e为该点的边数，所以复杂度降为O((m+n)logn)。

实现

1、将源点加入堆，并调整堆。

2、选出堆顶元素u（即代价最小的元素），从堆中删除，并对堆进行调整。

3、处理与u相邻的，未被访问过的，满足三角不等式的顶点

1) 若该点在堆里，更新距离，并调整该元素在堆中的位置。

2) 若该点不在堆里，加入堆，更新堆。

4、若取到的u为终点，结束算法；否则重复步骤2、3。

java 代码实现

  [java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//visit初始为0，防止回溯
int visit[] = new int[n+1];
//假设起点为src, 终点为dst, 图以二维矩阵的形式存储，若graph[i][j] == 0, 代表i,j不相连
int Dijkstra(int src, int dst, int[][] graph){
    PriorityQueue<Node> pq = new PriorityQueue<Node>();
    //将起点加入pq
    pq.add(new Node(src, 0));
    while(pq.size()){
        Node t = pq.poll();
        //当前节点是终点，即可返回最短路径
        if(t.node == dst) return t.cost;
        //若当前节点已遍历过，跳过当前节点
        if(visit[t.node]) continue;
        //将当前节点标记成已遍历
        visit[t.node] = 1;
        for(int i = 0; i < n; i++){
            if(graph[t.node][i] && !visited[i]){
                pq.add(new Node(i, t.cost + graph[t.node][i])); 
            }
        }
    }
    return -1
}

//定义一个存储节点和离起点相应距离的数据结构
class Node implements Comparator<Node> {
    public int node;
    public int cost;
   
    public Node()
    {
    }
   
    public Node(int node, int cost)
    {
        this.node = node;
        this.cost = cost;
    }
   
    @Override
    public int compare(Node node1, Node node2)
    {
        if (node1.cost < node2.cost)
            return -1;
        if (node1.cost > node2.cost)
            return 1;
        return 0;
    }
}

拓展阅读

图最短路径算法之弗洛伊德算法（Floyd）

贪心算法

参考资料

书籍

《大话数据结构》

blog

知乎-轻松搞懂dijkstra算法+堆优化 原理+实战

知乎-帮忙通俗解释一下Dijkstra算法

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

迪杰斯特拉（Dijkstra)算法最通俗易懂的讲解

迪杰斯特拉（Dijkstra)算法-百度百科

透彻理解迪杰斯特拉算法

迪杰斯特拉算法实现

深入理解 Dijkstra 算法实现原理

Dijkstra 算法代码实现

图(三,迪杰斯特拉算法)

[数据结构]迪杰斯特拉（Dijkstra）算法