"Tsinghua's" Algorithm
O(m + n log n)
→
O(m log
2/3
n)
Graph
(10v • 9e)
Simple Path
Cycle
Tree (Sparse)
Sparse Graph
Grid 5x5
Star Graph
Diamond
Medium Density
Dense Graph
Very Dense
Source
Target
*
Legend:
Source
Current
Visited
Queue
Pivot
Path
Undiscovered
Dijkstra's Algorithm
Not Started
↺ Reset
← Previous
▶ Play
Next →
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
0
0.0
1
∞
2
∞
3
∞
4
∞
5
∞
6
∞
7
∞
8
∞
9
∞
Tsinghua's Algorithm
Not Started
↺ Reset
← Previous
▶ Play
Next →
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
0
0.0
1
∞
2
∞
3
∞
4
∞
5
∞
6
∞
7
∞
8
∞
9
∞