Case

Source Node

Destination Node

Departure Time

Arrival Time

Shortest Time (Cost)

Path

Number of Explored Nodes

Polynomial LCA & Forward Dijkstra

a

5

2

9

16

7

5 à 3 à 2

5

b

5

2

15

24

9

5 à 3 à 1 à 2

5

c

5

2

16.75

26.25

9.5

5 à 3 à 2

5

Backward Dijkstra

a

2

5

9

16

7

2 à 3 à 5

4

b

2

5

15.5714

24

8.4286

2 à 3 à 5

4

c

2

5

19.25

26.25

7

2 à 3 à 5

4