Dijkstra算法原理及实现

算法原理

1. 简介

Dijkstra算法是从一个顶点到其余各顶点的最短路径(单源最短路径)算法，解决的是有向图中最短路径问题。算法的主要特点是使用了广度优先搜索策略，以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

2. 原理

1. 首先，引入一个辅助向量$D$，它的每个分量 $D [i]$保存当前所找到的从起始点$v$到其它每个顶点$v_i$的长度；一个保存已经找到了最短路径的顶点的集合：$T$
2. $D$的初始状态为: 若从$v$到$v_i$有弧，则$D[i]$为弧上的权值否则置$D[i]$为∞;
   $T$的初始状态为$\{v\}$
3. 从$D$数组选择最小值，则该值就是源点$v$到该值对应的顶点的最短路径，并且把该点加入到$T$中，OK，此时完成一个顶点
4. 然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点$D$中的值
5. 从$D$中找出最小值，重复上述动作，直到T中包含了图的所有顶点

算法演示

对于如下图，求顶点$v_1$到其他各点的最短路径

1. 初始化数$D = [0, inf, 10, inf, 30, 100]$, $T = \{v_1\}$

2. 当前离起始点$v_1$最近的点是$v_3$, 那么我们可以确定$v_1$和$v_3$的最近距离就是当前$D[2]$的值, 并将$v_3$加入$T$中 (为什么呢？因为目前离 v1顶点最近的是 v3顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得 v1顶点到 v3顶点的路程进一步缩短了。因为 v1顶点到其它顶点的路程肯定没有 v1到 v3顶点短.)

3. OK，既然确定了一个顶点的最短路径，下面我们就要根据这个新入的顶点$v_3$的出度，发现以$v_3$的出度的有：$\{v_4 \}$,那么我们看看路径：$v_1–v_3–v_4$的长度是否比$v_1–v_4$短，其实这个已经是很明显的了，因为$D[3]$代表的就是$v_1–v_4$的长度为无穷大，而$v_1–v_3–v_4$的长度为：10+50=60，所以更新$D[3]$的值,得到如下结果：

   $D = [0, inf, 10, 60, 30, 100]$, $T = \{v_1, v_3\}$

   (因此 $D[3]$要更新为 60。这个过程有个专业术语叫做“松弛”。即 $v_1$顶点到 $v_4$顶点的路程即 $D[3]$，通过 $v_3-v_4$这条边松弛成功。这便是 Dijkstra 算法的主要思想：通过“边”来松弛$v_1$顶点到其余各个顶点的路程)

4. 然后，我们又从除$v_1$和$v_3$外的其他值中寻找最小值，发现$D[4]$的值最小，通过之前是解释的原理，可以知道$v_1到v_5$的最短距离就是$D[4]$的值，然后，我们把$v_5$加入到集合T中，然后，考虑$v_5$的出度是否会影响我们的数组$D$的值，$v_5$有两条出度：$\{v_4, v_6\}$,然后我们发现：$v_1–v_5–v_4$的长度为：50，而$v_1-v_4$的值为60，所以我们要更新$D[3]$的值.另外，$v_1-v_5-v_6$的长度为：90，而$v_1-v_6$为100，所以我们需要更新$D[5]$的值。更新结果如下：

   $D = [0, inf, 10, 50, 30, 90]$, $T = \{v_1, v_3, v_5\}$

5. 继续从$D$中选择未确定的顶点的值中选择一个最小的值，发现$D[3]$的值是最小的，所以把$v_4$加入到集合$T$中，考虑$v_4$的出度，v4有一条出度：$\{v_6\}$,然后我们发现：$v_1–v_5–v_4–v_6$的长度为：60，而$v_1-v_6$的值为90，所以我们要更新$D[5]$的值, 结果如下

   $D = [0, inf, 10, 50, 30, 60]$, $T = \{v_1, v_3, v_5, v_4\}$

6. 用同样的方法确定了$v_6$和$v_2$的最短路径，得到的最终结果如下：

   $D = [0, inf, 10, 50, 30, 60]$, $T = \{v_1, v_3, v_5, v_4, v_6, v_2\}$

算法实现

# coding:utf-8
def dijkstra(G, v):
    """
    :param G: graph, type of dict
    :param v: original node, type of str
    :return: signal source shortest path,
    type of list
    """
    # initialize
    n = len(G)
    D = [float('inf')] * n
    D[node2ind(v)] = 0
    S = set(G.iterkeys())
    # iteration
    while S:
        v = None
        for node in S:
            if v == None or D[node2ind(node)] < D[node2ind(v)]:
                v = node
        S.remove(v)
        for node in G[v]:
            ind = node2ind(node)
            # 如果集合为空或者满足三角不等式，则更新D
            if D[node2ind(v)] + G[v][node] < D[ind]:
                D[ind] = D[node2ind(v)] + G[v][node]
    return D

def node2ind(node):
    """get index of node"""
    ind = int(node[-1]) - 1
    return ind

def ind2node(ind):
    """get node given index"""
    node = 'v' + str(ind + 1)
    return node


if __name__ == '__main__':
    G = {
        'v1':{'v3':10, 'v5':30, 'v6':100},
        'v2':{'v3':5},
        'v3':{'v4':50},
        'v4':{'v6':10},
        'v5':{'v4':20, 'v6':60},
        'v6':{}
         }
    v = 'v1'
    res = dijkstra(G, v)
    print(res)

"""打印的结果"""
[0, inf, 10, 50, 30, 60]

复杂度分析

该算法时间复杂度为$O(n^2)$, 但是，如果边数远小于$n^2$,对此可以考虑用堆这种数据结构进行优化，取出最短路径的复杂度降为$O(1)$；每次调整的复杂度降为$O(elogn)$；$e$为该点的边数，所以复杂度降为$O((m+n)logn)$, $m$为总的边数

堆优化算法步骤

1. 将与源点相连的点加入堆，并调整堆。
2. 选出堆顶元素$u$(即代价最小的元素），从堆中删除，并对堆进行调整。
3. 处理与$u$相邻的，未被访问过的，满足三角不等式的顶点
   1):若该点在堆里，更新距离，并调整该元素在堆中的位置。
   2):若该点不在堆里，加入堆，更新堆。
4. 若取到的$u$为终点，结束算法；否则重复步骤2、3。

堆优化算法实现

def dijkstra_heap(G, v):
    # initialize
    n = len(G)
    D = [float('inf')] * n
    D[node2ind(v)] = 0
    T = set()
    heap = []
    # iteration
    while len(T) < n:
        for node in G[v]:
                ind = node2ind(node)
                # 如果集合为空或者满足三角不等式，则更新D
                if len(T) == 0 or D[node2ind(v)] + G[v][node] < D[ind]:
                    D[ind] = D[node2ind(v)] + G[v][node]
                    heappush(heap, (D[node2ind(v)] + G[v][node], node))
        T.add(v)
        # find node minimum length to v
        if len(T) < n:
            node = heappop(heap)[1]
            while node in T:
                # 如果堆中没有元素了
                if not heap:
                    return D
                node = heappop(heap)[1]
            v = node
    return D

def node2ind(node):
    """get index of node"""
    ind = int(node[-1]) - 1
    return ind

def ind2node(ind):
    """get node given index"""
    node = 'v' + str(ind + 1)
    return node


if __name__ == '__main__':
    G = {
        'v1':{'v3':10, 'v5':30, 'v6':100},
        'v2':{'v3':5},
        'v3':{'v4':50},
        'v4':{'v6':10},
        'v5':{'v4':20, 'v6':60},
        'v6':{}
         }
    v = 'v1'
    res = dijkstra_heap(G, v)
    print(res)

"""打印的结果是"""
[0, inf, 10, 50, 30, 60]