Single-Source Shortest Paths

Example

Adjacency Matrix

	0	1	2	3	4	5	6
0	0	1	3	0	0	0	0
1	1	0	1	5	0	0	0
2	3	1	0	0	1	0	0
3	0	5	0	0	2	0	0
4	0	0	1	2	0	4	0
5	0	0	0	0	4	0	2
6	0	0	0	0	0	2	0

Dijkstra's Algorithm

Require non-negative weights

Time Complexity: $O((|E|+|V|)\log |V|)$ (use heap or priority queue) or $O(|E|+|V|\log |V|)$ (use Fibonacci heap min-priority queue)

Tests