Python/dynamic_programming/floyd_warshall.py at master · PreciousJac0b/Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
importmath


classGraph:
def__init__(self, n=0): # a graph with Node 0,1,...,N-1
self.n=n
self.w= [
 [math.infforjinrange(n)] foriinrange(n)
 ] # adjacency matrix for weight
self.dp= [
 [math.infforjinrange(n)] foriinrange(n)
 ] # dp[i][j] stores minimum distance from i to j

defadd_edge(self, u, v, w):
self.dp[u][v] =w

deffloyd_warshall(self):
forkinrange(self.n):
foriinrange(self.n):
forjinrange(self.n):
self.dp[i][j] =min(self.dp[i][j], self.dp[i][k] +self.dp[k][j])

defshow_min(self, u, v):
returnself.dp[u][v]


if__name__=="__main__":
graph=Graph(5)
graph.add_edge(0, 2, 9)
graph.add_edge(0, 4, 10)
graph.add_edge(1, 3, 5)
graph.add_edge(2, 3, 7)
graph.add_edge(3, 0, 10)
graph.add_edge(3, 1, 2)
graph.add_edge(3, 2, 1)
graph.add_edge(3, 4, 6)
graph.add_edge(4, 1, 3)
graph.add_edge(4, 2, 4)
graph.add_edge(4, 3, 9)
graph.floyd_warshall()
graph.show_min(1, 4)
graph.show_min(0, 3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
importmath


classGraph:
def__init__(self, n=0): # a graph with Node 0,1,...,N-1
self.n=n
self.w= [
 [math.infforjinrange(n)] foriinrange(n)
 ] # adjacency matrix for weight
self.dp= [
 [math.infforjinrange(n)] foriinrange(n)
 ] # dp[i][j] stores minimum distance from i to j

defadd_edge(self, u, v, w):
self.dp[u][v] =w

deffloyd_warshall(self):
forkinrange(self.n):
foriinrange(self.n):
forjinrange(self.n):
self.dp[i][j] =min(self.dp[i][j], self.dp[i][k] +self.dp[k][j])

defshow_min(self, u, v):
returnself.dp[u][v]


if__name__=="__main__":
graph=Graph(5)
graph.add_edge(0, 2, 9)
graph.add_edge(0, 4, 10)
graph.add_edge(1, 3, 5)
graph.add_edge(2, 3, 7)
graph.add_edge(3, 0, 10)
graph.add_edge(3, 1, 2)
graph.add_edge(3, 2, 1)
graph.add_edge(3, 4, 6)
graph.add_edge(4, 1, 3)
graph.add_edge(4, 2, 4)
graph.add_edge(4, 3, 9)
graph.floyd_warshall()
graph.show_min(1, 4)
graph.show_min(0, 3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
importmath


classGraph:
def__init__(self, n=0): # a graph with Node 0,1,...,N-1
self.n=n
self.w= [
 [math.infforjinrange(n)] foriinrange(n)
 ] # adjacency matrix for weight
self.dp= [
 [math.infforjinrange(n)] foriinrange(n)
 ] # dp[i][j] stores minimum distance from i to j

defadd_edge(self, u, v, w):
self.dp[u][v] =w

deffloyd_warshall(self):
forkinrange(self.n):
foriinrange(self.n):
forjinrange(self.n):
self.dp[i][j] =min(self.dp[i][j], self.dp[i][k] +self.dp[k][j])

defshow_min(self, u, v):
returnself.dp[u][v]


if__name__=="__main__":
graph=Graph(5)
graph.add_edge(0, 2, 9)
graph.add_edge(0, 4, 10)
graph.add_edge(1, 3, 5)
graph.add_edge(2, 3, 7)
graph.add_edge(3, 0, 10)
graph.add_edge(3, 1, 2)
graph.add_edge(3, 2, 1)
graph.add_edge(3, 4, 6)
graph.add_edge(4, 1, 3)
graph.add_edge(4, 2, 4)
graph.add_edge(4, 3, 9)
graph.floyd_warshall()
graph.show_min(1, 4)
graph.show_min(0, 3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
importmath


classGraph:
def__init__(self, n=0): # a graph with Node 0,1,...,N-1
self.n=n
self.w= [
 [math.infforjinrange(n)] foriinrange(n)
 ] # adjacency matrix for weight
self.dp= [
 [math.infforjinrange(n)] foriinrange(n)
 ] # dp[i][j] stores minimum distance from i to j

defadd_edge(self, u, v, w):
self.dp[u][v] =w

deffloyd_warshall(self):
forkinrange(self.n):
foriinrange(self.n):
forjinrange(self.n):
self.dp[i][j] =min(self.dp[i][j], self.dp[i][k] +self.dp[k][j])

defshow_min(self, u, v):
returnself.dp[u][v]


if__name__=="__main__":
graph=Graph(5)
graph.add_edge(0, 2, 9)
graph.add_edge(0, 4, 10)
graph.add_edge(1, 3, 5)
graph.add_edge(2, 3, 7)
graph.add_edge(3, 0, 10)
graph.add_edge(3, 1, 2)
graph.add_edge(3, 2, 1)
graph.add_edge(3, 4, 6)
graph.add_edge(4, 1, 3)
graph.add_edge(4, 2, 4)
graph.add_edge(4, 3, 9)
graph.floyd_warshall()
graph.show_min(1, 4)
graph.show_min(0, 3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
importmath


classGraph:
def__init__(self, n=0): # a graph with Node 0,1,...,N-1
self.n=n
self.w= [
 [math.infforjinrange(n)] foriinrange(n)
 ] # adjacency matrix for weight
self.dp= [
 [math.infforjinrange(n)] foriinrange(n)
 ] # dp[i][j] stores minimum distance from i to j

defadd_edge(self, u, v, w):
self.dp[u][v] =w

deffloyd_warshall(self):
forkinrange(self.n):
foriinrange(self.n):
forjinrange(self.n):
self.dp[i][j] =min(self.dp[i][j], self.dp[i][k] +self.dp[k][j])

defshow_min(self, u, v):
returnself.dp[u][v]


if__name__=="__main__":
graph=Graph(5)
graph.add_edge(0, 2, 9)
graph.add_edge(0, 4, 10)
graph.add_edge(1, 3, 5)
graph.add_edge(2, 3, 7)
graph.add_edge(3, 0, 10)
graph.add_edge(3, 1, 2)
graph.add_edge(3, 2, 1)
graph.add_edge(3, 4, 6)
graph.add_edge(4, 1, 3)
graph.add_edge(4, 2, 4)
graph.add_edge(4, 3, 9)
graph.floyd_warshall()
graph.show_min(1, 4)
graph.show_min(0, 3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
importmath


classGraph:
def__init__(self, n=0): # a graph with Node 0,1,...,N-1
self.n=n
self.w= [
 [math.infforjinrange(n)] foriinrange(n)
 ] # adjacency matrix for weight
self.dp= [
 [math.infforjinrange(n)] foriinrange(n)
 ] # dp[i][j] stores minimum distance from i to j

defadd_edge(self, u, v, w):
self.dp[u][v] =w

deffloyd_warshall(self):
forkinrange(self.n):
foriinrange(self.n):
forjinrange(self.n):
self.dp[i][j] =min(self.dp[i][j], self.dp[i][k] +self.dp[k][j])

defshow_min(self, u, v):
returnself.dp[u][v]


if__name__=="__main__":
graph=Graph(5)
graph.add_edge(0, 2, 9)
graph.add_edge(0, 4, 10)
graph.add_edge(1, 3, 5)
graph.add_edge(2, 3, 7)
graph.add_edge(3, 0, 10)
graph.add_edge(3, 1, 2)
graph.add_edge(3, 2, 1)
graph.add_edge(3, 4, 6)
graph.add_edge(4, 1, 3)
graph.add_edge(4, 2, 4)
graph.add_edge(4, 3, 9)
graph.floyd_warshall()
graph.show_min(1, 4)
graph.show_min(0, 3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
importmath


classGraph:
def__init__(self, n=0): # a graph with Node 0,1,...,N-1
self.n=n
self.w= [
 [math.infforjinrange(n)] foriinrange(n)
 ] # adjacency matrix for weight
self.dp= [
 [math.infforjinrange(n)] foriinrange(n)
 ] # dp[i][j] stores minimum distance from i to j

defadd_edge(self, u, v, w):
self.dp[u][v] =w

deffloyd_warshall(self):
forkinrange(self.n):
foriinrange(self.n):
forjinrange(self.n):
self.dp[i][j] =min(self.dp[i][j], self.dp[i][k] +self.dp[k][j])

defshow_min(self, u, v):
returnself.dp[u][v]


if__name__=="__main__":
graph=Graph(5)
graph.add_edge(0, 2, 9)
graph.add_edge(0, 4, 10)
graph.add_edge(1, 3, 5)
graph.add_edge(2, 3, 7)
graph.add_edge(3, 0, 10)
graph.add_edge(3, 1, 2)
graph.add_edge(3, 2, 1)
graph.add_edge(3, 4, 6)
graph.add_edge(4, 1, 3)
graph.add_edge(4, 2, 4)
graph.add_edge(4, 3, 9)
graph.floyd_warshall()
graph.show_min(1, 4)
graph.show_min(0, 3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
importmath


classGraph:
def__init__(self, n=0): # a graph with Node 0,1,...,N-1
self.n=n
self.w= [
 [math.infforjinrange(n)] foriinrange(n)
 ] # adjacency matrix for weight
self.dp= [
 [math.infforjinrange(n)] foriinrange(n)
 ] # dp[i][j] stores minimum distance from i to j

defadd_edge(self, u, v, w):
self.dp[u][v] =w

deffloyd_warshall(self):
forkinrange(self.n):
foriinrange(self.n):
forjinrange(self.n):
self.dp[i][j] =min(self.dp[i][j], self.dp[i][k] +self.dp[k][j])

defshow_min(self, u, v):
returnself.dp[u][v]


if__name__=="__main__":
graph=Graph(5)
graph.add_edge(0, 2, 9)
graph.add_edge(0, 4, 10)
graph.add_edge(1, 3, 5)
graph.add_edge(2, 3, 7)
graph.add_edge(3, 0, 10)
graph.add_edge(3, 1, 2)
graph.add_edge(3, 2, 1)
graph.add_edge(3, 4, 6)
graph.add_edge(4, 1, 3)
graph.add_edge(4, 2, 4)
graph.add_edge(4, 3, 9)
graph.floyd_warshall()
graph.show_min(1, 4)
graph.show_min(0, 3)