狄克斯特拉算法介紹

Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法是很有代表性的最短路徑算法，在很多專(zhuān)業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。注意該算法要求圖中不存在負(fù)權(quán)邊。
問(wèn)題描述：在無(wú)向圖 G=(V,E) 中，假設(shè)每條邊 E[i] 的長(zhǎng)度為 w[i]，找到由頂點(diǎn) V0 到其余各點(diǎn)的最短路徑。（單源最短路徑）

2.算法描述
(1)算法思想：設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖，把圖中頂點(diǎn)集合V分成兩組，第一組為已求出最短路徑的頂點(diǎn)集合（用S表示，初始時(shí)S中只有一個(gè)源點(diǎn)，以后每求得一條最短路徑 , 就將加入到集合S中，直到全部頂點(diǎn)都加入到S中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點(diǎn)集合（用U表示），按最短路徑長(zhǎng)度的遞增次序依次把第二組的頂點(diǎn)加入S中。在加入的過(guò)程中，總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長(zhǎng)度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長(zhǎng)度。此外，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離，S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長(zhǎng)度，U中的頂點(diǎn)的距離，是從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度。
(2)算法步驟：

a.初始時(shí)，S只包含源點(diǎn)，即S＝{v}，v的距離為0。U包含除v外的其他頂點(diǎn)，即:U={其余頂點(diǎn)}，若v與U中頂點(diǎn)u有邊，則<u,v>正常有權(quán)值，若u不是v的出邊鄰接點(diǎn)，則<u,v>權(quán)值為∞。

b.從U中選取一個(gè)距離v最小的頂點(diǎn)k，把k，加入S中（該選定的距離就是v到k的最短路徑長(zhǎng)度）。

c.以k為新考慮的中間點(diǎn)，修改U中各頂點(diǎn)的距離；若從源點(diǎn)v到頂點(diǎn)u的距離（經(jīng)過(guò)頂點(diǎn)k）比原來(lái)距離（不經(jīng)過(guò)頂點(diǎn)k）短，則修改頂點(diǎn)u的距離值，修改后的距離值的頂點(diǎn)k的距離加上邊上的權(quán)。

d.重復(fù)步驟b和c直到所有頂點(diǎn)都包含在S中。
引用自最短路徑—Dijkstra算法和Floyd算法

我的解釋

其實(shí)沒(méi)有這么難，對(duì)于我來(lái)說(shuō)，只有這幾步：
找出最快能到達(dá)的節(jié)點(diǎn)。
更新它鄰居的開(kāi)銷(xiāo)。
重復(fù)，再重復(fù)。
直到?jīng)]有未處理的節(jié)點(diǎn)。
感覺(jué)被世界上最?lèi)憾镜男【幩Ａ?/del>
別走！后面有料！

沒(méi)有高鐵的春運(yùn)難題

一個(gè)人，去一個(gè)農(nóng)家樂(lè)旅游，想要回到家鄉(xiāng)長(zhǎng)春，應(yīng)該怎么回去？
那個(gè)人畫(huà)了這張圖：

真是一個(gè)簡(jiǎn)潔的圖表

轉(zhuǎn)換為dict

graph = {
    'start.': {'Beijing': 5, 'TrainStation': 0, },
    'Beijing': {'ShanHaiGuan': 15, 'ShenYang': 20, },
    'ShanHaiGuan': {'ChangChun': 20, },
    'TrainStation': {'ShanHaiGuan': 30, 'ShenYang': 35, },
    'ShenYang': {'ChangChun': 10, },
    'ChangChun': None,
    }

用來(lái)存儲(chǔ)父節(jié)點(diǎn)和花銷(xiāo)的散列表類(lèi)似于這樣：

costs = {
    'Beijing': 5,
    'ShanHaiGuan': float('inf'),
    'TrainStation': 0,
    'ShenYang': float('inf'),
    'ChangChun': float('inf'),
    }
 
parents = {
    'Beijing': 'start.',
    'ShanHaiGuan': None,
    'TrainStation': 'start.',
    'ShenYang': None,
    'ChangChun': None,
    }

這只是為了方便讓您看懂。costs和parents散列表（dict）無(wú)需手動(dòng)實(shí)現(xiàn)，下面會(huì)告訴您如何自動(dòng)根據(jù)graph生成對(duì)應(yīng)的初始化的costs和parents。

Let's GO！

算法實(shí)現(xiàn)：

def find_quickest_way(graph, start, finish):
    # 根據(jù)圖生成花銷(xiāo)表
    costs = {}
    for k, v in graph.items():
        using_parents = graph[start]
        costs.update(using_parents)
        if k != start:
            if k not in using_parents.keys():
                costs[k] = float('inf')

    # 生成初始父節(jié)點(diǎn)表
    parents = {}
    for k, v in costs.items():
        if v == float('inf'):
            parents[k] = None
        else:
            parents[k] = start

    # 用來(lái)存儲(chǔ)處理過(guò)的節(jié)點(diǎn)
    processed = []

    # 最近的節(jié)點(diǎn)
    node = find_nearest_station(costs, processed)

    # 開(kāi)始狄克斯特拉算法
    while node is not None:
        # 如果最快的點(diǎn)是終點(diǎn)，則表明算法結(jié)束了
        if node == finish:
            break
        # 通向這個(gè)節(jié)點(diǎn)的花銷(xiāo)
        cost = costs[node]
        # 所有可以連接到的點(diǎn)
        neighbours = graph[node]
        for t, c in neighbours.items():
            # 新的花銷(xiāo)
            new_cost = cost + c
            # 如果花銷(xiāo)更小，使它的這個(gè)鄰居成為子節(jié)點(diǎn)
            if new_cost < costs[t]:
                costs[t] = new_cost
                parents[t] = node
            # 處理過(guò)了
            processed.append(node)
        # 最近的節(jié)點(diǎn)
        node = find_nearest_station(costs, processed)

    # 返回子父節(jié)點(diǎn)表
    return parents


def find_nearest_station(costs, processed):
    """傻瓜算法， 找到最快速的節(jié)點(diǎn)"""
    lowest_cost = float('inf')
    lowest_node = None
    for k in costs.keys():
        if costs[k] < lowest_cost and k not in processed:
            lowest_cost = costs[k]
            lowest_node = k
    return lowest_node

測(cè)試一下！

line = ['ChangChun']
# graph散列表見(jiàn)上文“沒(méi)有高鐵的春運(yùn)難題：轉(zhuǎn)換為dict”
my_parents = find_quickest_way(graph, 'start.', 'ChangChun')

while True:
    parent = my_parents[line[0]]
    line.insert(0, parent)
    if parent == 'start.':
        break

print(*line, sep=' => ')

start. => Beijing => ShenYang => ChangChun

Process finished with exit code 0

成功！

還記得最短路徑—Dijkstra算法和Floyd算法這個(gè)文章嗎？在開(kāi)頭提到過(guò)。這里面還有一個(gè)很好用的算法Floyd算法。