最短路算法算是基礎(chǔ)算法， 我還是總是忘。。維基有個(gè)動(dòng)圖很好，比較直觀，可是還不夠友好，于是自己做了點(diǎn)筆記，僅供參考。網(wǎng)上關(guān)于Dijkstra的文章也不少，適合的才是最好的。

動(dòng)態(tài)圖 - 來(lái)自wiki

Dijkstra_Animation.gif - 無(wú)向圖，正權(quán)值路徑

• 頂點(diǎn)為城市，頂點(diǎn)間連線表示城市相連通，線上數(shù)字為城市間距離。

  
  
  城市間距離

• 目標(biāo)為找出從序號(hào)為1的城市到序號(hào)為5的城市的最短路徑。

• 該路徑可以由 已知最短路徑 迭代求出。

• 每次從已知最短路徑中選出沒(méi)探索過(guò)且最短的，從該路徑終點(diǎn)出發(fā)，探索新的最短路徑。

• 一開(kāi)始，從出發(fā)點(diǎn)到達(dá)它之外的所有頂點(diǎn)的已知最短路徑為無(wú)窮大，到出發(fā)點(diǎn)自己的最短路徑為0。
  

• 現(xiàn)在，出發(fā)點(diǎn)的已知最短路徑最小，則從出發(fā)點(diǎn)出發(fā)，探索與其直連的所有頂點(diǎn)，如果路徑長(zhǎng)度比到該頂點(diǎn)的已知最短路徑小，則刷新該頂點(diǎn)的已知最短路徑。
  

• 接著，出發(fā)點(diǎn)已經(jīng)探索過(guò)了，從未出發(fā)探索過(guò)的已知最短路徑中選出最小的一個(gè)，即從城市2出發(fā)，探索與其直連的城市，如果到達(dá)該城市的路徑長(zhǎng)度比已知最短路徑小，則刷新最短路徑。可以看到，從城市2到3的路徑總長(zhǎng)17>城市3目前的最短路徑9，不滿(mǎn)足條件，不刷新城市3的最短路徑，而到城市4的已知最短路徑刷新為7+15=21。（已知最短路徑的計(jì)算都是從出發(fā)點(diǎn)開(kāi)始）
  

• 依次類(lèi)推，直到我們遇到目的地是已知最短路徑里未探索的所有頂點(diǎn)中最短的一個(gè)時(shí)，終止探索。

• 值得注意的是，我們每一步探索過(guò)程中的當(dāng)前出發(fā)點(diǎn)的最短路徑是確定的了，不會(huì)再變了，因?yàn)樗撬形刺剿鬟^(guò)的已知最短路徑中的最小的了，所以不存在從其它地方再加一段路程到達(dá)它還會(huì)比它更小的情況。

• 剛看動(dòng)態(tài)圖可能跟不上，我們用工具將gif轉(zhuǎn)為png一幀幀過(guò)一遍就好理解了， 圖在后面，先看代碼。

簡(jiǎn)單代碼

• 由維基百科里的偽代碼，可以比較簡(jiǎn)單地轉(zhuǎn)換為python代碼。

V = [ # 頂點(diǎn)列表
      1,  2,  3,  4,  5,  6]

w = [ # 城市間距離, -1表示無(wú)窮大，與圖中一致
    [ 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] # 出發(fā)點(diǎn)到各點(diǎn)的已知最短路徑的初始值, 到自身為0
    N = len(V) # 頂點(diǎn)數(shù)
    p = [None] * N # 出發(fā)點(diǎn)到各點(diǎn)的已知最短路徑的前一個(gè)點(diǎn)
    S = set() # 這個(gè)集合暫時(shí)沒(méi)什么用處
    Q = set(range(N)) # 生成所有頂點(diǎn)的虛擬序號(hào)的集合, 以0起始
    
    def Extract_Min(Q): # 將頂點(diǎn)集合Q中有最小d[u]值的頂點(diǎn)u從Q中刪除并返回u，可先不管
        u_min = None
        for u in Q:
            if d[u] != -1: # 無(wú)窮大則跳過(guò)
                u_min = u
        for u in Q:
            if d[u] == -1: # 無(wú)窮大則跳過(guò)
                continue
            if d[u_min] > d[u]:
                u_min = u
        Q.remove(u_min)
        return u_min
        
    v_d = V.index(dest) # 目的地的虛擬序號(hào)
    
    while Q : # 當(dāng)Q非空
        u = Extract_Min(Q) # 將頂點(diǎn)集合Q中有最小d[u]值的頂點(diǎn)u從Q中刪除并返回u
        if u == v_d : break # 可以在找到目的地之后立即終止，也可繼續(xù)查找完所有最短路徑
        S.add(u)
        
        v_reached_from_u = [i for i in range(N) if w[u][i] != -1] # u能到達(dá)的頂點(diǎn), 這里沒(méi)有去除在S中的頂點(diǎn)
        for v in v_reached_from_u:
            if d[v] > d[u] + w[u][v] or d[v] == -1: # 如果經(jīng)過(guò)u再到v的距離更短
                d[v] = d[u] + w[u][v] # 用該值更新已知最短路徑
                p[v] = u # 則已知到v的最短路徑上的倒數(shù)第二個(gè)點(diǎn)為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

使用堆

• 關(guān)鍵思路中從已知最短路徑中選擇最小的一個(gè)，還要增加（更新）新的值，讓人想到堆結(jié)構(gòu)。

• 利用python的堆結(jié)構(gòu)heapq，可以很簡(jiǎn)單地獲取到最小的已知最短路徑。
  

• 我們每次從堆中取出已知最短路徑中最短的，將從該點(diǎn)探索下的所有新路徑直接放入堆中，不用管重復(fù)，堆會(huì)返回有最小路徑的，只要我們額外使用一個(gè)集合來(lái)記錄已經(jīng)探索過(guò)的頂點(diǎn)即可，使每個(gè)頂點(diǎn)只探索一次。

• 先看沒(méi)有記錄路徑只算長(zhǎng)度的，代碼相對(duì)上面簡(jiǎn)潔了不少。

from heapq import heappop, heappush

V = [ # 頂點(diǎn)列表
      1,  2,  3,  4,  5,  6]

w = [ # 城市間距離, -1表示無(wú)窮大
    [ 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) # 頂點(diǎn)數(shù)
    S = set()
    Q = [(0, V.index(s))] # 路徑長(zhǎng)，城市虛擬序號(hào)
    
    v_d = V.index(dest)
    
    while Q : # 當(dāng)Q非空
        d, u = heappop(Q)
        if u == v_d : 
            print(d)
            break # 可以在找到目的地之后立即終止，也可繼續(xù)查找完所有最短路徑
        # 如果到目的地的距離已經(jīng)是當(dāng)前所有距離中最短的，那不可能會(huì)有更短的，所以退出
        if u not in S:
            S.add(u)
            v_reached_from_u = [i for i in range(N) if w[u][i] != -1] # u能到達(dá)的頂點(diǎn)
            for v in v_reached_from_u:
                if v not in S:
                    heappush(Q, ((d + w[u][v]), v)) # 到頂點(diǎn)v的某條路徑的距離
                    
Dijkstra() # 20

• 要記錄路徑，只需要在放入堆中的每個(gè)小元組尾部再加上個(gè)記號(hào)，改動(dòng)很少

from heapq import heappop, heappush

V = [ # 頂點(diǎn)列表
      1,  2,  3,  4,  5,  6]

w = [ # 城市間距離, -1表示無(wú)窮大
    [ 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) # 頂點(diǎn)數(shù)
    S = set()
    Q = [(0, V.index(s), str(s))] # 路徑長(zhǎng), 序號(hào), 路徑
    
    v_d = V.index(dest)
    
    while Q : # 當(dāng)Q非空
        d, u, p = heappop(Q) 
        if u == v_d : 
            print(d, p)
            break # 可以在找到目的地之后立即終止，也可繼續(xù)查找完所有最短路徑
        # 如果到目的地的距離已經(jīng)是當(dāng)前所有距離中最短的，那不可能會(huì)有更短的，所以退出
        if u not in S:
            S.add(u)
            v_reached_from_u = [i for i in range(N) if w[u][i] != -1] # u能到達(dá)的頂點(diǎn)
            for v in v_reached_from_u:
                if v not in S:
                    heappush(Q,(
                        (d + w[u][v]), v, ''.join((p,'->',str(V[v])))
                    )) # 到頂點(diǎn)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

工具

• 在網(wǎng)上找到的效果最好的從gif到png的轉(zhuǎn)化代碼

# 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')