Skip to content

Instantly share code, notes, and snippets.

@SudhakarReddyPeddinti

SudhakarReddyPeddinti/ShortestPathWithG[i,j]Weights

Created November 26, 2016 20:14
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save SudhakarReddyPeddinti/2bda39ad0777a63630fbfd2712a8ec7f to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save SudhakarReddyPeddinti/2bda39ad0777a63630fbfd2712a8ec7f to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. SudhakarReddyPeddinti created this gist Nov 26, 2016.
    170 changes: 170 additions & 0 deletions ShortestPathWithG[i,j]Weights
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,170 @@
    /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