Hello,朋友們。第二篇博客我們還是接著聊運動規(guī)劃算法。

上圖，圖中字母表示不同的地點，數(shù)字表示兩點之間的距離。我們要找到圖中的最短路徑，就拿A到E點做例子好了。

圖1

我們的目標(biāo)是：找到start-end之間的最短路徑，如圖所示

圖2

來吧，Dijkstra-迪杰斯特拉算法，這是一種基于貪心策略的動態(tài)規(guī)劃算法（后面解釋這句話），可以用來解決最短路徑問題。

首先把起點的距離設(shè)定為0（A到A當(dāng)然是0距離拉），然后把已經(jīng)確認(rèn)該點到起點之間的距離為最短距離的點標(biāo)紅（血統(tǒng)清晰）

圖3

下一步，我們考慮和A相鄰的點B，D， F ，把這些候選者們標(biāo)藍(lán)（血統(tǒng)不明）

圖4

很快我們就確定了A-B之間的最短距離為1，然后呢我們考慮B的相鄰下一站C。雖然A-C之間有3條路，A-B-C，A-D-C，A-B-D-C，但是目前我們只確定了A-B之間的最短距離，所以暫定A-C之間的距離為8

image.png

接下里，我們確認(rèn)A-D最短距離為2。這時候A-C之間的已知的最短距離更新了，為5。感覺越來越接近真相了哈。

圖5

接下來我們再確定了G點和E點后

圖6

我們最終確認(rèn)A-E之間的最短距離為6，我們得到了我們的目標(biāo)圖。

圖7

總結(jié)一下，事實總是逐漸揭露的，追隨著永恒的腳步，我獨自走在深藍(lán)的的路上說的就是這種算法。

整個過程用偽代碼表示就是：

image.png

這個算法計算復(fù)雜度的問題，從偽代碼中我們可以看出，實現(xiàn)需要兩層循環(huán)，第一層循環(huán)遍歷所有的結(jié)點，第二層循環(huán)遍歷每個節(jié)點周圍的路徑，所以，比較樸實的實現(xiàn)方法的話，計算復(fù)雜度為：

image.png

如果我們事先用優(yōu)先隊列PriorityQueue對節(jié)點進(jìn)行排序，可以降低計算復(fù)雜度：

image.png

其中，V是圖中節(jié)點的數(shù)量，E為路徑條數(shù)。

一般意義上的貪心算法在對問題求解時，總是做出在當(dāng)前看來是最好的選擇，也就是做出局部最優(yōu)解。迪杰斯特拉算法只考慮每個節(jié)點的最短路徑，然后從中再考慮到達(dá)相鄰節(jié)點的最短路徑，這符合了貪心策略。同時待求解的問題分解為若干個子問題，前一子問題的解，為后一子問題的求解提供了有用的信息這又符合了動態(tài)規(guī)劃的選擇。所以迪杰斯特拉算法是基于貪心策略的動態(tài)規(guī)劃算法，最后求出一定是整體最優(yōu)解。

下面附上python代碼：

from collections import defaultdict
class Graph:
  def __init__(self):
    self.nodes = set()
    self.edges = defaultdict(list)
    self.distances = {}

  def add_node(self, value):
    self.nodes.add(value)

  def add_edge(self, from_node, to_node, distance):
    self.edges[from_node].append(to_node)
    self.edges[to_node].append(from_node)
    self.distances[(from_node, to_node)] = distance
    self.distances[(to_node, from_node)] = distance


def dijsktra(graph, initial):
  visited = {initial: 0}
  path = {}

  nodes = set(graph.nodes)

  while nodes:
    min_node = None
    for node in nodes:
      if node in visited:
        if min_node is None:
          min_node = node
        elif visited[node] < visited[min_node]:
          min_node = node

    if min_node is None:
      break

    nodes.remove(min_node)
    current_weight = visited[min_node]

    for edge in graph.edges[min_node]:
      weight = current_weight + graph.distances[(min_node, edge)]
      if edge not in visited or weight < visited[edge]:
        visited[edge] = weight
        path[edge] = min_node

  return visited, path

g = Graph()

g.add_node('A')
g.add_node('B')
g.add_node('C')
g.add_node('D')
g.add_node('E')
g.add_node('F')
g.add_node('G')

g.add_edge('A','B',1)
g.add_edge('A','D',2)
g.add_edge('A','F',5)
g.add_edge('B','D',3)
g.add_edge('B','C',7)
g.add_edge('D','C',3)
g.add_edge('D','G',8)
g.add_edge('C','E',1)
g.add_edge('G','E',9)
g.add_edge('F','G',4)


print(dijsktra(g, 'E'))

({'E': 0, 'C': 1, 'G': 9, 'B': 7, 'D': 4, 'A': 6, 'F': 11}, {'C': 'E', 'G': 'E', 'B': 'D', 'D': 'C', 'A': 'D', 'F': 'A'})

另附github上很洋氣的解法：

from collections import defaultdict
from heapq import *

def dijkstra(edges, f, t):
    g = defaultdict(list)
    for l,r,c in edges:
        g[l].append((c,r))

    q, seen = [(0,f,())], set()
    while q:
        (cost,v1,path) = heappop(q)
        if v1 not in seen:
            seen.add(v1)
            path = (v1, path)
            if v1 == t: return (cost, path)

            for c, v2 in g.get(v1, ()):
                if v2 not in seen:
                    heappush(q, (cost+c, v2, path))

    return float("inf")

if __name__ == "__main__":
    edges = [
        ('A', 'B', 1),
        ('A', 'D', 2),
        ('A', 'F', 5),
        ('B', 'D', 3),
        ('B', 'C', 7),
        ('D', 'C', 3),
        ('D', 'G', 8),
        ('C', 'E', 1),
        ('G', 'E', 9),
        ('F', 'G', 4)
    ]

    print ("=== Dijkstra ===")
    print (edges)
    print ("A -> E:")
    print (dijkstra(edges, "A", "E"))

=== Dijkstra ===
[('A', 'B', 1), ('A', 'D', 2), ('A', 'F', 5), ('B', 'D', 3), ('B', 'C', 7), ('D', 'C', 3), ('D', 'G', 8), ('C', 'E', 1), ('G', 'E', 9), ('F', 'G', 4)]
A -> E:
(6, ('E', ('C', ('D', ('A', ())))))