CS2040s: Single-Source Shortest Path for graphs

Single Source Shortest Path

Weighted Graph

w(e) : E -> R

Each edge have a weight.

Shortest Path

Shortest path is not the minimum distance

- What is the path from a certain node to another?

- Shortest path from a node to every other node?

- Shortest path between every pair of node

We cant use BFS because it finds the minimum number of hops not minimum distance.
Minimum distance is not the shortest path due to the weights the edges hold.

Minimum distance -> sum of edges weight

Minimum hops -> Least number of nodes passing to get to destination

#1 If all weights are positive, can the shortest path contain a cycle? => no

PROOF
by contradiction

Suppose the shortest path p is not a simple path
[A simple path have no repeated vertex meaning no cycle]

Then p must contain at least one cycle c

Suppose there is a cycle c in p with positive weight

If we remove c then we have a shorter path then the previous shortest path
There was not suppose to have another shortest path.

CONTRADICTION! 

Conclusion: P is a simple path

Even in non positive weight,

0 weight cycle can be remove even if it occurs
ie 0 weight cycles does not matter

Negative weight cycles are bad
=> Infinite loop

#2 If the graph have no negative weight cycles, shortest path from source is a simple path

The shortest path can at most have |v| - 1 edges

#3 Triangle Inequality
In a triangle the base is either shorter or equal to the sum of the other two edges

Assume the shortest path is k

k < = a + w

where a and w is not the base of the triangle

By proving by contradiction, assume that

k> a + w

Then k is not the shortest path already since we can take a+w as the path 

Relaxing (Finding shortest path)

Reduce estimate distance between two points s and u

Invariant: Estimate d[s,u] > = p[s,u]

p is shortest path and d is distance

relax(int u, int v){
  if (dist[v] > dist[u] + weight(u,v))
    dist[v] = dist[u] + weight(u,v);
}

Key idea:
Test if to
get from s -> v, v -> x
is shorter than the path s->x

Using relax to find shortest path

1. Set all node distance except the original node as infinite

The starting node is 0

2. Check the setted distance of the first neighbour

if setted distance is larger than (edge + prev node distance), update the edge with the sum
else move on to the next neighbour for this current node
3. Repeat till reach the end
4. Backtrack and repeat from step 2 until all path have been explored

//step 2 is my relax step

#4 Upper Bound property

The distance will always be > = shortest path

Once minimum distance = shortest path, the minimum distance never changes

Proof by Induction

#5 Convergence Property

If u is a predecessor of v in some shortest path to v, and d(u) = δ(u), then after relaxing (u,v), d(v) = δ(v). By the monotonocity and upper-bound properties, d(v) = δ(v) forever after.

If there is some path that is the shortest path from s to v,
no matter how many relaxation is done between s and v,
by upper bound property, the distance and shortest path will always remain the same.

If we have a certain path from s to v and it is the shortest path.

This property holds regardless if other relaxation occurs.

E.g

The shortest path is e1e2e3e4

even if we do e1e1e1e1e1e2e3e4, the shortest distance still holds

(Even if intermix)

#6 Path relaxation Property

If p is a shortest from from v to u then once we relax the edges of p (Look at all possible edges from v to u), then d[u] = p[u] for all nodes
ie. We can get every shortest subpath

Proof:
BY INDUCTION

1. Base case: Source node (0)

Assume that some path from 0 to k-1 is correct

d[v(k-1)] = p[v(k-1)] 

2. Inductive step

when we relax (find the shortest path already), 

d[v(k)] = p[v(k-1)]  +w(e)

= p[v(k)]
where w(e) is the weight of the edge between k-1 and k

Relax algo will not always work
=> For all edge in graph we relax

Because we go through every edge once
=> The last edge needs to be gone through 3 times to find shortest path

BellMan- Ford Algorithm

Find the shortest distance to all path from a specific node s
by making using of relaxing but using relax for each vertices present in the graph

ie. do not just go through the vertices once

If there are no neg weight, after bellman ford algo terminate, we will get the shortest distance

BellmanFord(V,E)
 n = V.length
 for i = 1 to n-1
    for Edge e in E //relax part
         relax(e)

Proof

k<|v| - 1 where k is how long p can be (shortest path)

At each iteration we relax all e edges,

by path relaxation property, after |v| - 1 iteration,

d[t =V(k)] = s [t =V(k)]

The runtime is O(VE)

We can terminate when an entire of |E| relax operation have no effect within one for loop of edges

This will work almost the same for negative weights.. almost
It will not be able to work if there is a negative cycle.

Same weight:

Just run BFS

Negative cycles:

Main idea: Run bellman-ford for V iteration,

if estimate changes in last iteration then neg cycle

- Run the for loop one more time

for every edge

      if need relax

         return false //Theres negative cycles

 return true

Trees (Redefine)

A tree has only one way to get to one location to another without backpedaling
This is due to a tree property.

Undirected Tree

- Graph with no cycle is an undirected tree

Rooted Tree

A tree with a special designated root node

Source to all
What is the cost to get to all the places?
Shortest Path:
We should relax the nodes using DFS Order
=> we want to visit every node
=> Once we update a node, we never have to update it again
This is because all nodes can be access in one way only
This works for negative weights as well.

The running time is O(v) or O(e)
=> All nodes got 1 parent
=> Edges = v - 1