n = 10 m = 30 s = 0 t = 9 +++ Reading edges 5 2 9 4 2 0 5 6 4 1 6 9 3 7 0 4 4 3 3 6 6 1 3 1 1 7 2 8 1 3 2 4 6 7 1 8 8 4 4 5 3 9 0 8 2 3 5 4 7 4 7 8 5 9 5 3 1 9 3 5 +++ The generated graph 0 -> 8, 4 1 -> 9, 8, 3, 7 2 -> 3, 4, 8, 0 3 -> 5, 9, 1, 6, 7 4 -> 5, 3, 1 5 -> 3, 9, 4, 6, 2 6 -> 7, 1, 9 7 -> 8, 4 8 -> 4 9 -> 4 +++ Reading edge weights wt( 0,8 ) = 0.9 wt( 0,4 ) = 0.7 wt( 1,9 ) = 0.5 wt( 1,8 ) = 0.9 wt( 1,3 ) = 0.7 wt( 1,7 ) = 0.1 wt( 2,3 ) = 0.2 wt( 2,4 ) = 0.8 wt( 2,8 ) = 0.8 wt( 2,0 ) = 0.6 wt( 3,5 ) = 0.3 wt( 3,9 ) = 0.3 wt( 3,1 ) = 1.0 wt( 3,6 ) = 0.2 wt( 3,7 ) = 0.3 wt( 4,5 ) = 0.2 wt( 4,3 ) = 0.8 wt( 4,1 ) = 0.3 wt( 5,3 ) = 0.7 wt( 5,9 ) = 0.5 wt( 5,4 ) = 0.1 wt( 5,6 ) = 0.2 wt( 5,2 ) = 0.6 wt( 6,7 ) = 0.8 wt( 6,1 ) = 0.7 wt( 6,9 ) = 0.1 wt( 7,8 ) = 0.6 wt( 7,4 ) = 0.8 wt( 8,4 ) = 1.0 wt( 9,4 ) = 0.9 +++ Reading vertex weights wt(0) = 19 wt(1) = 10 wt(2) = 14 wt(3) = 10 wt(4) = 6 wt(5) = 10 wt(6) = 16 wt(7) = 7 wt(8) = 6 wt(9) = 5 +++ Running Dijkstra on the original graph --- Shortest (0,9) distance is 1.200000 --- Shortest (0,9) path: 0 - 4 - 5 - 6 - 9 +++ Changing the edge weights Edge weight (0,8) changes from 0.9 to 0.105361 Edge weight (0,4) changes from 0.7 to 0.356675 Edge weight (1,9) changes from 0.5 to 0.693147 Edge weight (1,8) changes from 0.9 to 0.105361 Edge weight (1,3) changes from 0.7 to 0.356675 Edge weight (1,7) changes from 0.1 to 2.302585 Edge weight (2,3) changes from 0.2 to 1.609438 Edge weight (2,4) changes from 0.8 to 0.223144 Edge weight (2,8) changes from 0.8 to 0.223144 Edge weight (2,0) changes from 0.6 to 0.510826 Edge weight (3,5) changes from 0.3 to 1.203973 Edge weight (3,9) changes from 0.3 to 1.203973 Edge weight (3,1) changes from 1.0 to 0.000000 Edge weight (3,6) changes from 0.2 to 1.609438 Edge weight (3,7) changes from 0.3 to 1.203973 Edge weight (4,5) changes from 0.2 to 1.609438 Edge weight (4,3) changes from 0.8 to 0.223144 Edge weight (4,1) changes from 0.3 to 1.203973 Edge weight (5,3) changes from 0.7 to 0.356675 Edge weight (5,9) changes from 0.5 to 0.693147 Edge weight (5,4) changes from 0.1 to 2.302585 Edge weight (5,6) changes from 0.2 to 1.609438 Edge weight (5,2) changes from 0.6 to 0.510826 Edge weight (6,7) changes from 0.8 to 0.223144 Edge weight (6,1) changes from 0.7 to 0.356675 Edge weight (6,9) changes from 0.1 to 2.302585 Edge weight (7,8) changes from 0.6 to 0.510826 Edge weight (7,4) changes from 0.8 to 0.223144 Edge weight (8,4) changes from 1.0 to 0.000000 Edge weight (9,4) changes from 0.9 to 0.105361 +++ Running Dijkstra on the log-converted graph --- Shortest (0,9) distance is 1.021651 --- Shortest (0,9) path: 0 - 8 - 4 - 3 - 1 - 9 +++ Converting vertex weights to edge weights 0 -> 1 1 -> 8, 16 2 -> 3 3 -> 14, 6, 16, 18 4 -> 5 5 -> 0, 16, 8, 6 6 -> 7 7 -> 14, 12, 2, 18, 10 8 -> 9 9 -> 2, 6, 10 10 -> 11 11 -> 4, 12, 8, 18, 6 12 -> 13 13 -> 18, 2, 14 14 -> 15 15 -> 8, 16 16 -> 17 17 -> 8 18 -> 19 19 -> 8 +++ Running Dijkstra on the vertex-weight graph --- Shortest (0,9) distance is 40.000000 --- Shortest (0,9) path: 0 - 4 - 5 - 9