Dijkstra最短路算法笔记

最短路算法算是基础算法， 我还是总是忘。。维基有个动图很好，比较直观，可是还不够友好，于是自己做了点笔记，仅供参考。网上关于Dijkstra的文章也不少，适合的才是最好的。

动态图 - 来自wiki

Dijkstra_Animation.gif - 无向图，正权值路径

• 顶点为城市，顶点间连线表示城市相连通，线上数字为城市间距离。

  
  城市间距离

• 目标为找出从序号为1的城市到序号为5的城市的最短路径。

• 该路径可以由 已知最短路径 迭代求出。

• 每次从已知最短路径中选出没探索过且最短的，从该路径终点出发，探索新的最短路径。

• 一开始，从出发点到达它之外的所有顶点的已知最短路径为无穷大，到出发点自己的最短路径为0。
  

  

• 现在，出发点的已知最短路径最小，则从出发点出发，探索与其直连的所有顶点，如果路径长度比到该顶点的已知最短路径小，则刷新该顶点的已知最短路径。
  

  

• 接着，出发点已经探索过了，从未出发探索过的已知最短路径中选出最小的一个，即从城市2出发，探索与其直连的城市，如果到达该城市的路径长度比已知最短路径小，则刷新最短路径。可以看到，从城市2到3的路径总长17>城市3目前的最短路径9，不满足条件，不刷新城市3的最短路径，而到城市4的已知最短路径刷新为7+15=21。（已知最短路径的计算都是从出发点开始）
  

  

• 依次类推，直到我们遇到目的地是已知最短路径里未探索的所有顶点中最短的一个时，终止探索。

• 值得注意的是，我们每一步探索过程中的当前出发点的最短路径是确定的了，不会再变了，因为它是所有未探索过的已知最短路径中的最小的了，所以不存在从其它地方再加一段路程到达它还会比它更小的情况。

• 刚看动态图可能跟不上，我们用工具将gif转为png一帧帧过一遍就好理解了， 图在后面，先看代码。

简单代码

• 由维基百科里的伪代码，可以比较简单地转换为python代码。

V = [ # 顶点列表
      1,  2,  3,  4,  5,  6]

w = [ # 城市间距离, -1表示无穷大，与图中一致
    [ 0,  7,  9, -1, -1, 14],
    [ 7,  0, 10, 15, -1, -1],
    [ 9, 10,  0, 11, -1,  2],
    [-1, 15, 11,  0,  6, -1],
    [-1, -1, -1,  6,  0,  9],
    [14, -1,  2, -1,  9,  0]]

def Dijkstra(V=V, w=w, s=1, dest=5):
    d = [-1 if v != s else 0 for v in V] # 出发点到各点的已知最短路径的初始值, 到自身为0
    N = len(V) # 顶点数
    p = [None] * N # 出发点到各点的已知最短路径的前一个点
    S = set() # 这个集合暂时没什么用处
    Q = set(range(N)) # 生成所有顶点的虚拟序号的集合, 以0起始
    
    def Extract_Min(Q): # 将顶点集合Q中有最小d[u]值的顶点u从Q中删除并返回u，可先不管
        u_min = None
        for u in Q:
            if d[u] != -1: # 无穷大则跳过
                u_min = u
        for u in Q:
            if d[u] == -1: # 无穷大则跳过
                continue
            if d[u_min] > d[u]:
                u_min = u
        Q.remove(u_min)
        return u_min
        
    v_d = V.index(dest) # 目的地的虚拟序号
    
    while Q : # 当Q非空
        u = Extract_Min(Q) # 将顶点集合Q中有最小d[u]值的顶点u从Q中删除并返回u
        if u == v_d : break # 可以在找到目的地之后立即终止，也可继续查找完所有最短路径
        S.add(u)
        
        v_reached_from_u = [i for i in range(N) if w[u][i] != -1] # u能到达的顶点, 这里没有去除在S中的顶点
        for v in v_reached_from_u:
            if d[v] > d[u] + w[u][v] or d[v] == -1: # 如果经过u再到v的距离更短
                d[v] = d[u] + w[u][v] # 用该值更新已知最短路径
                p[v] = u # 则已知到v的最短路径上的倒数第二个点为u
        print('d=', d)
    
    v = v_d  # 由p列表可以回溯出最短路径
    final_route = []
    while v != V.index(s):
        final_route.insert(0, str(V[v]))
        v = p[v]
    final_route.insert(0, str(V[v]))
    print('最终路径', '-->'.join(final_route))

        
Dijkstra()
#d= [0, 7, 9, -1, -1, 14]
#d= [0, 7, 9, 22, -1, 14]
#d= [0, 7, 9, 20, -1, 11]
#d= [0, 7, 9, 20, 20, 11]
#最终路径 1-->3-->6-->5

使用堆

• 关键思路中从已知最短路径中选择最小的一个，还要增加（更新）新的值，让人想到堆结构。

• 利用python的堆结构heapq，可以很简单地获取到最小的已知最短路径。
  

  

• 我们每次从堆中取出已知最短路径中最短的，将从该点探索下的所有新路径直接放入堆中，不用管重复，堆会返回有最小路径的，只要我们额外使用一个集合来记录已经探索过的顶点即可，使每个顶点只探索一次。

• 先看没有记录路径只算长度的，代码相对上面简洁了不少。

from heapq import heappop, heappush

V = [ # 顶点列表
      1,  2,  3,  4,  5,  6]

w = [ # 城市间距离, -1表示无穷大
    [ 0,  7,  9, -1, -1, 14],
    [ 7,  0, 10, 15, -1, -1],
    [ 9, 10,  0, 11, -1,  2],
    [-1, 15, 11,  0,  6, -1],
    [-1, -1, -1,  6,  0,  9],
    [14, -1,  2, -1,  9,  0]]

def Dijkstra(V=V, w=w, s=1, dest=5):
    N = len(V) # 顶点数
    S = set()
    Q = [(0, V.index(s))] # 路径长，城市虚拟序号
    
    v_d = V.index(dest)
    
    while Q : # 当Q非空
        d, u = heappop(Q)
        if u == v_d : 
            print(d)
            break # 可以在找到目的地之后立即终止，也可继续查找完所有最短路径
        # 如果到目的地的距离已经是当前所有距离中最短的，那不可能会有更短的，所以退出
        if u not in S:
            S.add(u)
            v_reached_from_u = [i for i in range(N) if w[u][i] != -1] # u能到达的顶点
            for v in v_reached_from_u:
                if v not in S:
                    heappush(Q, ((d + w[u][v]), v)) # 到顶点v的某条路径的距离
                    
Dijkstra() # 20

• 要记录路径，只需要在放入堆中的每个小元组尾部再加上个记号，改动很少

from heapq import heappop, heappush

V = [ # 顶点列表
      1,  2,  3,  4,  5,  6]

w = [ # 城市间距离, -1表示无穷大
    [ 0,  7,  9, -1, -1, 14],
    [ 7,  0, 10, 15, -1, -1],
    [ 9, 10,  0, 11, -1,  2],
    [-1, 15, 11,  0,  6, -1],
    [-1, -1, -1,  6,  0,  9],
    [14, -1,  2, -1,  9,  0]]

def Dijkstra(V=V, w=w, s=1, dest=5):
    N = len(V) # 顶点数
    S = set()
    Q = [(0, V.index(s), str(s))] # 路径长, 序号, 路径
    
    v_d = V.index(dest)
    
    while Q : # 当Q非空
        d, u, p = heappop(Q) 
        if u == v_d : 
            print(d, p)
            break # 可以在找到目的地之后立即终止，也可继续查找完所有最短路径
        # 如果到目的地的距离已经是当前所有距离中最短的，那不可能会有更短的，所以退出
        if u not in S:
            S.add(u)
            v_reached_from_u = [i for i in range(N) if w[u][i] != -1] # u能到达的顶点
            for v in v_reached_from_u:
                if v not in S:
                    heappush(Q,(
                        (d + w[u][v]), v, ''.join((p,'->',str(V[v])))
                    )) # 到顶点v的某条路径的距离
                    
Dijkstra() # 20 1->3->6->5

分解图 - 使用文末工具

Dijkstra_Animation-0.png Dijkstra_Animation-1.png Dijkstra_Animation-2.png Dijkstra_Animation-3.png Dijkstra_Animation-4.png Dijkstra_Animation-5.png Dijkstra_Animation-6.png Dijkstra_Animation-7.png Dijkstra_Animation-8.png Dijkstra_Animation-9.png Dijkstra_Animation-10.png Dijkstra_Animation-11.png Dijkstra_Animation-12.png Dijkstra_Animation-13.png Dijkstra_Animation-14.png Dijkstra_Animation-15.png Dijkstra_Animation-16.png Dijkstra_Animation-17.png Dijkstra_Animation-18.png Dijkstra_Animation-19.png Dijkstra_Animation-20.png Dijkstra_Animation-21.png Dijkstra_Animation-22.png Dijkstra_Animation-23.png Dijkstra_Animation-24.png Dijkstra_Animation-25.png Dijkstra_Animation-26.png

工具

• 在网上找到的效果最好的从gif到png的转化代码

# https://gist.github.com/BigglesZX/4016539
import os
from PIL import Image


'''
I searched high and low for solutions to the "extract animated GIF frames in Python"
problem, and after much trial and error came up with the following solution based
on several partial examples around the web (mostly Stack Overflow).
There are two pitfalls that aren't often mentioned when dealing with animated GIFs -
firstly that some files feature per-frame local palettes while some have one global
palette for all frames, and secondly that some GIFs replace the entire image with
each new frame ('full' mode in the code below), and some only update a specific
region ('partial').
This code deals with both those cases by examining the palette and redraw
instructions of each frame. In the latter case this requires a preliminary (usually
partial) iteration of the frames before processing, since the redraw mode needs to
be consistently applied across all frames. I found a couple of examples of
partial-mode GIFs containing the occasional full-frame redraw, which would result
in bad renders of those frames if the mode assessment was only done on a
single-frame basis.
Nov 2012
'''


def analyseImage(path):
    '''
    Pre-process pass over the image to determine the mode (full or additive).
    Necessary as assessing single frames isn't reliable. Need to know the mode 
    before processing all frames.
    '''
    im = Image.open(path)
    results = {
        'size': im.size,
        'mode': 'full',
    }
    try:
        while True:
            if im.tile:
                tile = im.tile[0]
                update_region = tile[1]
                update_region_dimensions = update_region[2:]
                if update_region_dimensions != im.size:
                    results['mode'] = 'partial'
                    break
            im.seek(im.tell() + 1)
    except EOFError:
        pass
    return results


def processImage(path):
    '''
    Iterate the GIF, extracting each frame.
    '''
    mode = analyseImage(path)['mode']
    
    im = Image.open(path)

    i = 0
    p = im.getpalette()
    last_frame = im.convert('RGBA')
    
    try:
        while True:
            print("saving %s (%s) frame %d, %s %s" % (path, mode, i, im.size, im.tile))
            
            '''
            If the GIF uses local colour tables, each frame will have its own palette.
            If not, we need to apply the global palette to the new frame.
            '''
            if not im.getpalette():
                im.putpalette(p)
            
            new_frame = Image.new('RGBA', im.size)
            
            '''
            Is this file a "partial"-mode GIF where frames update a region of a different size to the entire image?
            If so, we need to construct the new frame by pasting it on top of the preceding frames.
            '''
            if mode == 'partial':
                new_frame.paste(last_frame)
            
            new_frame.paste(im, (0,0), im.convert('RGBA'))
            new_frame.save('%s-%d.png' % (''.join(os.path.basename(path).split('.')[:-1]), i), 'PNG')

            i += 1
            last_frame = new_frame
            im.seek(im.tell() + 1)
    except EOFError:
        pass

# 使用
import os
os.chdir(r'E:\python\2017_3_1\dijkst\png')
processImage('E:/python/2017_3_1/dijkst/Dijkstra_Animation.gif')