Floyd algorithm used to find the shortest distance between two points (multi-source shortest path), is a typical dynamic programming

The principle is simple: there can be one of two shortest paths from point I to point j:

  1. Direct to (I –> j)
  2. By going the other points (k1, k2… Kn), one or more points arrive (I –> K1 –> K2 –>… –> j )

So you find the shortest path and you just compare 1 and 2 to see which path is shorter

Data structure: adjacency matrix (n*n) graph, graph[I][j] represents the shortest path I -> j. Graph [I][j] == 0, graph[I][j] == 0, graph[I][j] = edge weight

To find the shortest path from I to j, we need I to go through another node and go back to j (I -> k -> j), see which path is shorter than the original path (I -> j), and then update graph[I][j]. And to do that you have to go through each node.

Here’s a demonstration. For example, we can only through the Numbers for 1 nodes first, — — > I j and I — — — — > > 1 j, which is small, the way and then update the I – > j of the shortest path graph [I] [j] = min (graph [I] [j], graph[ i ][ 1 ] + graph[ 1 ][ j ] )

for i in range(n):
	for j in range(n):
		graph[i][j] = min(graph[i][j], graph[i][1] + graph[1][j])
Copy the code

And the same thing goes through some other point, let’s say 2

for i in range(n):
	for j in range(n):
		graph[i][j] = min(graph[i][j], graph[i][2] + graph[2][j])
Copy the code

Finally, we have to go through each point:

for k in range(n):
	for i in range(n):
		for j in range(n):
			graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
Copy the code

Isn’t it easy… The core code is only 4 lines of code…

Because every time the path I -> j is updated to the best and saved, the next node is guaranteed to be optimal by going through this node to other nodes.

Example: Images from:www.cnblogs.com/wangyuliang…More on that in this blog post

To print the path, we need to record the parent of each node with a two-dimensional array, parents. Update the parent node when the shortest path is found. Finally, find the parent recursively and print back.

import sys

sys.setrecursionlimit(100000000)


# Freudian algorithm
def floyd() :
    n = len(graph)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if graph[i][k] + graph[k][j] < graph[i][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
                    parents[i][j] = parents[k][j]  Update the parent


# print path
def print_path(i, j) :
    ifi ! = j: print_path(i, parents[i][j])print(j, end='-->')


# Data [u, v, cost]
datas = [
    [0.1.2],
    [0.2.6],
    [0.3.4],
    [1.2.3],
    [2.0.7],
    [2.3.1],
    [3.0.5],
    [3.2.12],
]

n = 4

# infinity
inf = 9999999999

# composition
graph = [[(lambda x: 0 if x[0] == x[1] else inf)([i, j]) for j in range(n)] for i in range(n)]
parents = [[i] * n for i in range(4)]  The key point is that the parent of I ->j is initialized to I
for u, v, c in datas:
    graph[u][v] = c	Graph [u][v]
    #graph[v][u] = c #

floyd()

print('Costs:')
for row in graph:
    for e in row:
        print('up' if e == inf else e, end='\t')
    print(a)print('\nPath:')
for i in range(n):
    for j in range(n):
        print('Path({}-->{}): '.format(i, j), end=' ')
        print_path(i, j)
        print(' cost:', graph[i][j])

# Final graph
# graph[I][j] represents the shortest path I ->j
0, 2, 5, 4
9, 0, 3, 4
Number 6, 8, 0, 1
Number 5, 7, 10, 0
#
# Path:
# Path(0-->0): 0--> cost: 0
# Path(0-->1): 0-->1--> cost: 2
# Path(0-->2): 0-->1-->2--> cost: 5
# Path(0-->3): 0-->3--> cost: 4
# Path(1-->0): 1-->2-->3-->0--> cost: 9
# Path(1-->1): 1--> cost: 0
# Path(1-->2): 1-->2--> cost: 3
# Path(1-->3): 1-->2-->3--> cost: 4
# Path(2-->0): 2-->3-->0--> cost: 6
# Path(2-->1): 2-->3-->0-->1--> cost: 8
# Path(2-->2): 2--> cost: 0
# Path(2-->3): 2-->3--> cost: 1
# Path(3-->0): 3-->0--> cost: 5
# Path(3-->1): 3-->0-->1--> cost: 7
# Path(3-->2): 3-->0-->1-->2--> cost: 10
# Path(3-->3): 3--> cost: 0
Copy the code