CS2040s: Shortest path (Special Cases)

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

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

Update the current shortest path when a shorter path is found

(relax)

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.

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 

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

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.

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.

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

DFS: Vertex that was discovered most recently

DIjkstra: Vertex that is closest to the  source

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)