Cheng: Graph - Shortest Path Tree (SPT)

Shortest path TREE -

given a start vertex from a graph, find the shortest path to all other vertices, that is, shortest path tree.

Consider vertices in increasing order of distance from s.
Add vertex to tree and relax all edges pointing from that vertex.
Running time: O(|E|.Tdk + |V|.Tem), where Tdk is the running time to decrease priority of a vertex in Priority-Queue, Tem is the running time to extract min value from priority queue and this is typically O(1) for different implementation of priority queue. Tdk depends on different implementation of priority queue, and worth research on that. [TODO]
since it consider vertex which is closet to source, so the path which the last second vertex is closest to source will be found first if ecmp exists.

to select vertex in increasing order of distance from s means to greedily select closest unprocessed vertex which probably requires a priority-queue to extract closest vertex.
since the distance to each vertex has been updated dynamically during the edges relaxation, so the priority-queue must support methods like increase_priority()
but to increase the priority of an element, one has to find it at first. how to find an element efficiently in a priority-queue?
a heap implemented priority-queue is not good at searching/finding which implies we need advanced data structures, such as Fibonacci-heap etc.

if we generate a shortest path tree, obviously there is only one path from s to other vertices. in this case, it could be stored as simply as an array with n length, each element in the array stores its previous vertex.
a general requirement is to store all the paths from s to t, which requires to support ecmp (equal-cost multi-path). that makes the results a graph instead of a tree. however, if the results are just stored as a graph, when retrieving a path (s, t), one has to use path finding algorithms, like dfs, to search again. as an alternative, we could improve the retrieve performance with the price of more memory consumption.

Relax - test if we can improve the shortest path to a vertex v found so far by passing through another vertex
runs in O(|V|.|E|) time

works for graph with negative weights, but not negative cycles
run one more iteration, then we can detect if there is negative cycle.
also, this algorithm does not support ecmp. (actually we can view ecmp as a matter of storage or data structure instead of algorithm itself) if this case, path with minimal hops will be found first.
Question: if we relax the edges as different order, for a specific path (s, t), is it possible that we could have different path when ecmp exists?

a dynamic programming example solving all-pairs shortest path
running time O(|V|^3), suitable for dense graph; for sparse graph, run Dijkstra for every vertex could be an alternative with running time O(|V|.|E|.log(|V|) using binary-heap)
support edges with negative weight but no negative cycle in graph
recursive formula:

shortestPath(i, j) = min{shortestPath(i, j), shortestPath(i, k) + c(k, j) try every k }

Cheng