Algorithms -- Paths in graphs
Distances
The distance between two nodes is the length of the shortest path them
BFS -- Breadth First Search
Different from DFS, the BFS aims at the shortest path which can be backward constructed if we record the prev node.
procedure bfs(G,s){
// Input: Graph G = (V, E), directed or undirected; From vertex s in V
// Output: For all vertices u reachable from s, dist(u) is the distance from s to u
for all u in V: dist(u) = \infty
dist(s) = 0;
Q = {s};
while Q is not empty:
u = pop(Q)
for all edges (u,v) in E:
if dist(v) = \infty
push(Q, v);
dist(v) = dist(u) + 1;
The queue is FILO
Dijkstra's Algorithm
Assuming the length or weigh is give on edges. We need to deal with it when we try to figure out the shortest route from the source to specific node.
procedure dijkstra(G, l, s){
for all u in V:
dist(u) = \infty;
prev(u) = null;
dist(s) = 0;
H = makequeue(V) \\using dist-values a keys
while H is not empty:
H = popMin(H);
for all edges (u,v) in E:
if dist(v) > dist(u) + l(u,v):
dist(v) = dist(u) + l(u,v);
prev(v) = u;
decreaseKey(H, v);
However, here is an assumption: There is no negative edge in E
Priority queue
The priority queue as a data structure should support such operations:
- Insert
- getMin
- decreaseKey
And there are several implementations:
- Array (with sort method)
- Binary Heap (it can be realized as an array)
- D-ary Heap ( the amount of children is d rather than original 2)
- Fibonacci Heap (a little sophisticated)
Bellman-Ford Algorithm
For those containing negative edges, we can update very frequently
procedure update( (u,v) in E)
dist(v) = min( dist(v), dist(u) + l(u,v) );
procedure bellman-ford(G,l,s){
for all u in V:
dist(u) = \infty
prev(u) = null
dist(s) = 0;
repeat |V| -1 times:
for all e in E:
update(e)
And actually, for DAG, we can solve the problem in linear time. The difference is that we need to linearize G before updating, and the order of updating is in linearized order.