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

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

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

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

  
  
  城市間距離

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

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

• 每次從已知最短路徑中選出沒探索過且最短的性昭，從該路徑終點(diǎn)出發(fā)拦止，探索新的最短路徑。

• 一開始，從出發(fā)點(diǎn)到達(dá)它之外的所有頂點(diǎn)的已知最短路徑為無窮大汹族，到出發(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)探索過了坑资，從未出發(fā)探索過的已知最短路徑中選出最小的一個(gè)耗帕，即從城市2出發(fā)，探索與其直連的城市袱贮，如果到達(dá)該城市的路徑長(zhǎng)度比已知最短路徑小仿便，則刷新最短路徑≡芪。可以看到嗽仪，從城市2到3的路徑總長(zhǎng)17>城市3目前的最短路徑9，不滿足條件柒莉，不刷新城市3的最短路徑闻坚，而到城市4的已知最短路徑刷新為7+15=21。（已知最短路徑的計(jì)算都是從出發(fā)點(diǎn)開始）
  

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

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

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

簡(jiǎn)單代碼

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

V = [ # 頂點(diǎn)列表
      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] # 出發(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í)沒什么用處
    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: # 無窮大則跳過
                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) # 目的地的虛擬序號(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), 這里沒有去除在S中的頂點(diǎn)
        for v in v_reached_from_u:
            if d[v] > d[u] + w[u][v] or d[v] == -1: # 如果經(jīng)過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è)集合來記錄已經(jīng)探索過的頂點(diǎn)即可赏酥，使每個(gè)頂點(diǎn)只探索一次。

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

from heapq import heappop, heappush

V = [ # 頂點(diǎn)列表
      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) # 頂點(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表示無窮大
    [ 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')