最短路徑算法

Dijkstra算法

理解

function Dijkstra(G, w, s)
   for each vertex v in V[G]         # 初始化
         d[v] := infinity             # 將各點(diǎn)的已知最短距離先設(shè)成無窮大
         previous[v] := undefined     # 各點(diǎn)的已知最短路徑上的前趨都未知
   d[s] := 0                         # 因?yàn)槌霭l(fā)點(diǎn)到出發(fā)點(diǎn)間不需移動(dòng)任何距離，所以可以直接將s到s的最小距離設(shè)為0
   S := empty set
   Q := set of all vertices
   while Q is not an empty set       # Dijkstra演算法主體
         u := Extract_Min(Q)
         S.append(u)
         for each edge outgoing from u as (u,v)
                if d[v] > d[u] + w(u,v)       # 拓展邊（u,v）。w(u,v)為從u到v的路徑長(zhǎng)度。
                      d[v] := d[u] + w(u,v)   # 更新路徑長(zhǎng)度到更小的那個(gè)和值。
                      previous[v] := u        # 紀(jì)錄前趨頂點(diǎn)

實(shí)現(xiàn)

import sysclass Graph():
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for _ in range(self.V)] for _ in range(self.V)]
    # 打印距離
    def print_distance(self, dist, parent):
        for node in range(self.V):
            print('distance')
            print(node, dist[node])
            print('path')
            self.print_path(parent, node)
            print('---------')
    # 打印路徑
    def print_path(self, parent, j):
        if parent[j] == -1:
            print(j)
            return
        self.print_path(parent, parent[j])
        print(j)
    # 找出最小距離的結(jié)點(diǎn)
    def min_distance(self, dist, sptSet):
        min_val = sys.maxsize
        min_index = 0
        for v in range(self.V):
            if dist[v] < min_val and not sptSet[v]:
                min_val = dist[v]
                min_index = v
        return min_index
    # 核心算法
    def dijkstra(self, src):
        dist = [sys.maxsize] * self.V
        dist[src] = 0
        sptSet = [False] * self.V
        parent = [-1] * self.V
        for count in range(self.V):
            # 找出前驅(qū)結(jié)點(diǎn)
            u = self.min_distance(dist, sptSet)
            sptSet[u] = True
            # 如果某個(gè)節(jié)點(diǎn)的路徑大于經(jīng)過前驅(qū)結(jié)點(diǎn)的路徑，則更新結(jié)果成經(jīng)過前驅(qū)結(jié)點(diǎn)的路徑
            for v in range(self.V):
                if self.graph[u][v] > 0 and not sptSet[v] and dist[v] > dist[u] + self.graph[u][v]:
                    dist[v] = dist[u] + self.graph[u][v]
                    parent[v] = u
        self.print_distance(dist, parent)g = Graph(8)g.graph = [[0, 0, 7, 7, 2, 0, 0, 0],
           [0, 0, 3, 8, 0, 0, 8, 0],
           [7, 3, 0, 0, 0, 7, 0, 0],
           [7, 8, 0, 0, 0, 0, 0, 0],
           [2, 0, 0, 0, 0, 0, 0, 8],
           [0, 0, 7, 0, 0, 0, 8, 0],
           [0, 8, 0, 0, 0, 8, 0, 6],
           [0, 0, 0, 0, 8, 0, 6, 0]]g.dijkstra(0)

Floyd

理解

實(shí)現(xiàn)

import copyINF = 1e9class Graph():
    def __init__(self, graph):
        self.V = len(graph)
        self.graph = graph
    # 打印距離
    def print_distance(self, dist):
        for i in range(self.V):
            for j in range(self.V):
                print('%5s' % (dist[i][j] if dist[i][j] != INF else 'INF'), end='')
            print('')
    # 核心算法
    def floydwarshall(self):
        dist = copy.deepcopy(self.graph)
        for k in range(self.V):
            for i in range(self.V):
                for j in range(self.V):
                    # 不考慮自己指向自己的情況
                    if i == j:
                        continue
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        self.print_distance(dist)g = Graph([[INF, INF, 1, INF, INF, INF, INF, INF],
           [INF, INF, 2, 8, INF, 5, INF, INF],
           [9, INF, INF, INF, 2, INF, INF, INF],
           [INF, INF, INF, INF, INF, 2, INF, INF],
           [INF, INF, INF, INF, INF, INF, INF, 9],
           [INF, INF, INF, INF, INF, INF, INF, INF],
           [INF, INF, INF, INF, 1, INF, INF, INF],
           [INF, INF, INF, INF, INF, 7, 7, INF]])g.floydwarshall()