CS2040s: Shortest path (Special Cases)

Recap

Simple path

There are no cycles, if a graph contains no negative weight cycles then the shortest path is a simple path where

it has at most v - 1 edges

Shortest Path

Maintain estimate for each distance: Relax(s,B)

Update the current shortest path when a shorter path is found

(relax)

The subpath of shortest path are always the shortest path.

BellManFord

We dont know the shortest path, so we use bellman ford to relax all the edges.

Relaxing all the edges will allow us to cover the correct edge to relax.

We only need to repeat the iteration for v-1 iterations 

Set all distance to infinity at first. 

Later we update. This ensure that we can identify when the path is  disconnected

Order:

Any Order is fine.

Storing the shortest path:

Update it when we update the shortest path

Use an array to store the shortest path.

Dijkstra's Algorithm

Key idea: Relax the edges in the right order, relaxing the shortest weight. 

Works on graph with non negative edges.

Only relax each edge once.

- Maintain distance estimate for every node

- Begin with empty shortest path tree

1. Start at node s

2. Add the s into the queue

3. Remove s and relax

4. Update the paths and add it to 

5. Look at the node in the queue with the minimum distance, relax that node

6. repeat 4

Basically only update/relax the neighbour with what seems to be the smallest distance.

Stop when you reach the end

Dijkstra(G, s)
  create vertex set Q
  for each v in G
       dist[v] = INFTY
       prev[v] = UNDEF
   dist[s] = 0
   while Q is not empty
        u = vertex in Q with min dist[u]
        remove u from Q
        for each neighbor v of u:
               relax(u,v)
    return dist, prev 

Use a PQ as the data structure to store the path distance

-> AVL trees , (heap is fine)

Time complexity: O((V+E) LogV)
-> Insert/delMin O(V), each node is added to pq once
-> Relax/decreaseKey O(E), each edge relax once

-> PQ is LogV

Proof: Induction

Every finish vertex has a correct estimate.

Base case:

The source itself is the shortest path

Inductive step:

Proof by contradiction. 

Assume the shortest path is not the shortest path.

The real path have distance r

There will be a contradiction because pq ensure that only the smallest will be taken out.

Negative weights

Destroy the proof.

Dystra only look at the smallest distance but there might be a case where adding a negative will make the other path shorter but we fail to look at that because we only pick the smallest edge in that instance

Re-Weight will not work, we do not preserve the shortest path.

Comparison to BFS and DFS

Maintain a set of explored vertices.

Add vertices to explored set (hashmap) by following edges that go from a vertex in the explored set to a vertex outside explored set

BFS: Vertex that was discovered least recently

DFS: Vertex that was discovered most recently

DIjkstra: Vertex that is closest to the  source

Directed Acyclic Graph

1. Topological sort

2. Relax in order

-> Relax the neighbours first

This is because DAG is in order and has no cycles

Time Complexity-> O(V+E)