FilesExpand file tree

master

/

floydwarshall.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

72 lines (52 loc) · 1.79 KB

master

/

floydwarshall.py

Copy path

Top

File metadata and controls

• Code
• Blame

72 lines (52 loc) · 1.79 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

# floyd warshall all pair shortest path

# java code https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/FloydWarshallAllPairShortestPath.java

import sys

INF = 1000000

class NegativeWeightCycleException(Exception):

def __init__(self):

pass

def all_pair_shortest_path(distance_matrix):

size = len(distance_matrix)

distance = [[0 for x in range(size)]

for x in range (size)]

path = [[0 for x in range(size)]

for x in range (size)]

for i in range(size):

for j in range(size):

distance[i][j] = distance_matrix[i][j]

if distance_matrix[i][j] != INF and i != j:

path[i][j] = i

else:

path[i][j] = -1

for k in range(size):

for i in range(size):

for j in range(size):

if distance[i][k] == INF or distance[k][j] == INF:

continue

if distance[i][j] > distance[i][k] + distance[k][j]:

distance[i][j] = distance[i][k] + distance[k][j]

path[i][j] = path[k][j]

for i in range(size):

if distance[i][i] < 0:

raise NegativeWeightCycleException()

print_path(path, 3, 2)

return (distance, path)

def print_path(path, start, end):

stack = []

stack.append(end)

while True:

end = path[start][end]

if end == -1:

return

stack.append(end)

if end == start:

break

print(stack[::-1])

if __name__ == '__main__':

distance_matrix = [[0, 3, 6, 15],

[INF, 0, -2, INF],

[INF, INF, 0, 2],

[1, INF, INF, 0]]

distance, path = all_pair_shortest_path(distance_matrix)

print(distance)

#print(path)