Floyd-warshall算法

问题描述

图的最短路径问题，多源最短路径问题求解

算法思路

• 设D_ij^k为从i到j的只以(1...k)集合为中间节点的最短路径的长度，D_ij^k = min(D_ij^k-1， D_ik^k-1 + D_kj^k-1)

  若最短路径经过点k,则D_ij^k = D_ik^k-1 + D_kj^k-1;

  若最短路径不经过点k,则D_ij^k = D_ij^k-1

python代码如下：

graph = {'A':[(2, 'A', 'B')],
         'B':[(1, 'B', 'C'), (6, 'B', 'D')],
         'C':[(5, 'C', 'A'), (4, 'C', 'D')],
         'D':[(3, 'D', 'A')], 
        }
def graph2adjacent_matrix(graph):
    vertices = list(graph.keys())
    vnum = len(vertices)
    adjacent_matrix = [[0 if row == col else float('inf') for col in range(vnum)] for row in range(vnum)]
    for i in range(vnum):
        vertex = vertices[i]
        for edge in graph[vertex]:
            w, _, end_vertex = edge
            j = vertices.index(end_vertex)
            adjacent_matrix[i][j] = w
    return adjacent_matrix


def floyd(adjacent_matrix):
    vnum = len(adjacent_matrix)
    a = [[adjacent_matrix[row][col] for col in range(vnum)] for row in range(vnum)]
    nvertex = [[-1 if adjacent_matrix[row][col] == float('inf') else row for col in range(vnum)] for row in range(vnum)]
    for k in range(vnum):
        for i in range(vnum):
            for j in range(vnum):
                if a[i][j] > a[i][k] + a[k][j]:
                    a[i][j] = a[i][k] + a[k][j]
                    nvertex[i][j] = nvertex[k][j]
    return nvertex, a

adjacent_matrix = graph2adjacent_matrix(graph)
nvertex, a = floyd(adjacent_matrix)

for i in range(len(adjacent_matrix)):
    for j in range(len(adjacent_matrix[0])):
        print(adjacent_matrix[i][j], end='\t')
    print()
print('------------------------------------------------------------------------')
for i in range(len(nvertex)):
    for j in range (len(nvertex[0])):
        print(nvertex[i][j], end = '\t')
    print()
print('------------------------------------------------------------------------')
for i in range(len(a)):
    for j in range(len(a[0])):
        print(a[i][j], end='\t')
    print()
    

算法改进

• 先比较再相加

  若D_ik^k-1 或D_kj^k-1 > D_ij^k,则最短路径不经过点k,则D_ij^k = D_ij^k-1

  若D_ik^k-1 < D_ij^k且 D_kj^k-1 < D_ij^k,则最短路径可能经过点k,则D_ij^k = min(D_ij^k-1， D_ik^k-1 + D_kj^k-1)

• 不难发现，对于每个点k,D_ik^k 以及D_kj^k是不会更新的，故可以添加约束条件：

  if D_ik^k = 0，i++

  if D_kj^k = 0，j++

• 若点i与点k之间没有路径，那么点i到点j的最短路径一定不经过点k，故可添加约束条件：

  if D_ik^k-1 == inf, i++

  if D_kj^k-1 == inf, j++

python代码如下：

def floyd(adjacent_matrix):
    vnum = len(adjacent_matrix)
    a = [[adjacent_matrix[row][col] for col in range(vnum)] for row in range(vnum)]
    nvertex = [[-1 if adjacent_matrix[row][col] == float('inf') else row for col in range(vnum)] for row in range(vnum)]
    for k in range(vnum):
        for i in range(vnum):
            if (a[i][k] == 'inf')| (i == k):
                continue
            for j in range(vnum):
                if (a[k][j] == 'inf')| (k == j):
                    continue
                elif (a[i][j] > a[i][k]) & (a[i][j] > a[k][j]):
                    if a[i][j] > a[i][k] + a[k][j]:
                        a[i][j] = a[i][k] + a[k][j]
                        nvertex[i][j] = nvertex[k][j]
    return nvertex, a