Skip to content

Instantly share code, notes, and snippets.

@SudhakarReddyPeddinti

SudhakarReddyPeddinti/ShortestPathWithG[i,j]Weights

Created November 26, 2016 20:14
Show Gist options
  • Save SudhakarReddyPeddinti/2bda39ad0777a63630fbfd2712a8ec7f to your computer and use it in GitHub Desktop.
Save SudhakarReddyPeddinti/2bda39ad0777a63630fbfd2712a8ec7f to your computer and use it in GitHub Desktop.
Download ZIP
Shortest path recalculation with G[i][j] as edge weights to observe the impact.
Raw
ShortestPathWithG[i,j]Weights
/Library/Frameworks/Python.framework/Versions/3.5/bin/python3.5 /Users/sudhakar/Documents/Gits/Shortest_Path_In_Congestion/Shortest_Path_In_Congestion/CongestionHandler.py
Floyd Warshall shortest path distances:
0 7 9 7 13 9
12 0 5 13 9 3
7 9 0 8 4 6
9 4 2 0 6 7
3 5 10 10 0 8
15 5 8 10 12 0
Floyd Warshall Graph Paths
(1) (1,2) (1,4,3) (1,4) (1,4,3,5) (1,6)
(2,3,5,1) (2) (2,3) (2,3,4) (2,3,5) (2,6)
(3,5,1) (3,5,2) (3) (3,4) (3,5) (3,6)
(4,1) (4,2) (4,3) (4) (4,3,5) (4,2,6)
(5,1) (5,2) (5,3) (5,4) (5) (5,2,6)
(6,3,5,1) (6,2) (6,3) (6,4) (6,3,5) (6)
Hop count:
0 1 2 1 3 1
3 0 1 2 2 1
2 2 0 1 1 1
1 1 1 0 2 2
1 1 1 1 0 2
3 1 1 1 2 0
Load_matrix:
0 9 na 31 na 12
na 0 60 na 0 52
0 0 0 24 132 10
17 26 46 0 na na
68 43 12 14 0 na
na 16 42 8 na 0
Actual edge delay matrix:
0 19.6 na 79.33 na 21.0
na 0 42.5 na 10.0 42.0
9.0 10.0 0 29.33 180.0 13.5
30.86 15.56 11.2 0 na na
207.0 48.0 23.33 150.0 0 na
na 85.0 120.0 18.89 na 0
Actual path delay matrix:
0 19.6 90.53 79.33 270.53 21.0
429.5 0 42.5 71.83 222.5 42.0
387.0 228.0 0 29.33 180.0 13.5
30.86 15.56 11.2 0 191.2 57.56
207.0 48.0 23.33 150.0 0 90.0
507.0 85.0 120.0 18.89 300.0 0
The shortest predicted path length between a:2 and b:1 is 12
The actual path length between a:2 and b:1 is 429.5
The actual path length and the predicted path length are within 97.21 of each other
The shortest path between a:2 and b:1 is [2, 3, 5, 1]
The predicted edge lengths from first and last edge on the path are:
Edge_path, Predicted_edge_length, Actual_edge_length
(2, 3) 5 42.5
(3, 5) 4 180.0
(5, 1) 3 207.0
Hop count is 3
[[0, 19.6, 9999999, 79.33, 9999999, 21.0], [9999999, 0, 42.5, 9999999, 10.0, 42.0], [9.0, 10.0, 0, 29.33, 180.0, 13.5], [30.86, 15.56, 11.2, 0, 9999999, 9999999], [207.0, 48.0, 23.33, 150.0, 0, 9999999], [9999999, 85.0, 120.0, 18.89, 9999999, 0]]
Floyd Warshall shortest path distances:
0 19.6 51.09 39.89 29.6 21.0
42.33 0 33.33 60.89 10.0 42.0
9.0 10.0 0 29.33 20.0 13.5
20.2 15.56 11.2 0 25.56 24.7
32.33 33.33 23.33 52.66 0 36.83
39.09 34.45 30.09 18.89 44.45 0
Floyd Warshall Graph Paths
(1) (1,2) (1,6,4,3) (1,6,4) (1,2,5) (1,6)
(2,5,3,1) (2) (2,5,3) (2,6,4) (2,5) (2,6)
(3,1) (3,2) (3) (3,4) (3,2,5) (3,6)
(4,3,1) (4,2) (4,3) (4) (4,2,5) (4,3,6)
(5,3,1) (5,3,2) (5,3) (5,3,4) (5) (5,3,6)
(6,4,3,1) (6,4,2) (6,4,3) (6,4) (6,4,2,5) (6)
Hop count:
0 2 5 3 5 2
6 0 3 4 3 2
3 3 0 2 3 2
3 2 2 0 4 4
3 3 2 3 0 4
6 3 3 2 5 0
Load_matrix:
0 26 na 31 na 47
na 0 60 na 94 80
85 37 0 52 132 54
17 76 135 0 na na
68 43 111 14 0 na
na 16 42 107 na 0
Actual edge delay matrix:
0 INF na 899.07 na INF
na 0 361.25 na INF INF
INF INF 0 INF 8100.0 INF
105.81 INF INF 0 na na
14283.0 460.8 INF 2250.0 0 na
na 1445.0 1800.0 INF na 0
Actual path delay matrix:
0 INF INF INF INF INF
INF 0 INF INF INF INF
INF INF 0 INF INF INF
INF INF INF 0 INF INF
INF INF INF INF 0 INF
INF INF INF INF INF 0
The shortest predicted path length between a:2 and b:1 is 42.33
The actual path length between a:2 and b:1 is INF
The actual path length and the predicted path length are within 100.0 of each other
The shortest path between a:2 and b:1 is [2, 5, 3, 1]
The predicted edge lengths from first and last edge on the path are:
Edge_path, Predicted_edge_length, Actual_edge_length
(2, 5) 999999 INF
(5, 3) 999999 INF
(3, 1) 999999 INF
Hop count is 3
Process finished with exit code 0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment