39. Graphs-5: Shortest Path

Topics-

Relaxation...

# Topo shortest distance

# BFS shortest distance (unit weights)

# Dijkstra            (all, except negative weights)
# Bellmen Ford   (all, except negative cycles) 
# Floyd Warshall (multi source)
# Shortest path     (path reconstruction)
----------------------------------
1. Word ladder-1,2
2. Shortest Path in binary matrix
3. Min Effort Path⭐
4. Cheapest Flights within K stops⭐
5. Min multiplications
6. City with smallest no. of neighbours within threshold
7. No. of ways to reach a destination⭐
---------------------------------------------------------------------------------------------------------------

# Topo Shortest Dist Algo

time: O(V+E)

- only for weighted DAGs
- works even for negative edge weights
- works because in topo sorted order of nodes (nodes appearing before dependants), distance propagates correctly.
------------------
1. Perform topo sort & let it be stored in the stack
2. Declare dist array (with dist to each node as INF & dist to src node as 0) 
3. Keep popping out elements from stack & for each element, relax its neighbours

----------------------------------------------------------------------------------------------------------------------------

# BFS Shortest Dist Algo

- only for graphs with weight = 1
- works for both directed and undirected graphs (even for cyclic graphs)
- not for weighted graphs
- This is a special case of dijkstra when weight = 1
-------------------------

Approach- 
- since BFS explores layer by layer, hence shortest dist to reach a node = first time we reach it through BFS

- so we do normal BFS, except that we perform relaxation of current node's neighbours and if relaxed then we push them into queue.

-----------------------------------------------------------------------------------------------------------------------------

# Dijkstra Algorithm
(optimal)

time: O( ElogV )
---------

- Finds shortest dist from src node to every other node
- works for both directed & undirected weighted graphs which may contain cycles.

- Not for (-ve) weighted graphs (as it will fall into infinite loop). Then use Bellman ford

---------------------
- It is greedy BFS ( always expand the node with smallest current distance )
- Uses min heap based priority queue ( it optimises the order of exploration- sorted by shortest distance so far)
---------------------------------------

do BFS with dist array & perform relaxation, before pushing {dist, node} into pq

relaxation: dist[v] = min(dist[v], dist[u] + uv) 
where dist[i] means dist to reach i-th node from src

----------------------------------------------------------------------------------------------------------------------------

## Dijkstra Algorithm
(alter implementation)

- uses set
- saves a few iterations as it erases bad version immediately (unlike pq based implementation where we keep all versions, skip bad ones later )

---------------------
- every logic is same, except an edge case. e.g.,

dist array has 10 at posn 5 & we got a 8 at posn 5 at some point of time, so we can erase 10,5 from set at this point, so some iterations will be saved where else wise, we would have checked 10,5 from set, even after updating 8,5 into it as well as the dist array
-------------------------

----------------------------------------------------------------------------------------------------------------------------

## Dijkstra Algorithm
(brute)

- uses queue
- this method will include storing distances of all paths.
- here, nodes may enter the queue multiple times until dist[] stabilises

---------------------------------------------------------------------------------------------------------------------------

# Shortest Path:

Finding shortest path from src to destination node
----------------
- using modified dijkstra
- needs a parent [] , initialised with p[i] = i
- in original dijkstra, we now store parent element of every node which gets relaxed
- hence we now know how we reached every node optimally

Hence we can reconstruct the path from destination to src node by backtracking in the parent vector at the end and finally reversing the path to get answer

----------------------------------------------------------------------------------------------------------------------------

# Bellmen ford algorithm-

time: O(E*V)

- it is a DP based algorithm
- less optimal than dijkstra

- finds shortest dist b/w 2 nodes, even if negative wts are present 
- helps in negative cycle detection
- not find shortest path if negative cycle exists

- only for Directed Graphs
- can also work for undirected graphs, if we represent them as directed

---------------------------
Approach-
- Do (N-1) iterations s.t in each iteration, you go through all edges & relax them.

- After all (N-1) iterations, we get final reduced distance array (which shouldn't be further reduced)
- Check, if it can be further reduced, then a (-ve) cycle exists.

-----------------------------------------------------------------------------------------------------------------------------

# Floyd Warshall Algorithm-

(all pairs shortest path algo)

- Finds shortest path from any src node to any destination node

- Also help in detecting (-ve) cycles
- it is brute force, where we explore all possible paths.
---------------

# Approach-
- Go via every node
- uses adjacency matrix
- It uses DP to find shortest path: d[i][j] = min{ d[i][k] + d[k][j], dp[i][j] }
  where dp[i][j] means min cost to go from i to j

---------------------------------------------------
# Observation-
1. initial cost matrix
2. via 0 wale mein pichle wale (initial matrix) ki 0th row same copied here
3. via 1 wale mein pichle wale (via 0 matrix) ki 1th row same copied here
and so on....

----------------------------------------------------------

# We can also detect a negative cycle using floyd warshall-

if any m[i][i] !=0 => negative cycle exists

--------------------------------------------------------------------------------------------------------------

Note-
We can also use dijkstra to find all pair shortest distance:
by applying dijkstra to every node which would result in (V*ElogV) time complexity
but it won't account for negative cycles.

----------------------------------------------------------------------------------------------------------------------------

1. Word Ladder-I

we can imagine it as a graph with each node as a word and each edge as meaning 2 words differing by exactly 1 character. Since, every transformation costs 1 step, hence we use BFS

Instead of creating graph first and then working on it,
we will prefer to generate neighbours dynamically during BFS traversal

For every word we will change each character by trying all a-z combinations. If generated word exists in dictionary then edge exists and we push it into queue.
We use a set for constant lookup. 

----------------------------------------------------------------------------------------------------------------------------

2. Word Ladder-II🔥

non intuitive
( not for interviews )

(complexity of this soln- unpredictable)

- ek level waali saari lists ki same length hogi
- ek level ki saari lists pe kaam krne ke baad, jo last elements use hue the har list mein, unko og dict mein se remove krdo.
- do not remove a word from dict unless we have worked upon every lists in a level where this word was last word.
- if at any time, while traversing diff levels in queue, you find in a list that, the last word is ending word, then put it into ans and put all similar lengths lists into ans and when lengths exceed stop.

-----------------------------------------------------------------------------------------------------------------------------

3. Shortest Path in a Binary Matrix-

Find shortest dist in a binary grid, to go from top left cell to bottom right cell,
if u can only move through 0s in 8 directions
----------------------
Approach:
- since here, every direction takes unit dist so we prefer BFS  

- we will use (visited matrix) + (queue storing {posn, dist} )
- we can also do it using, (dist matrix) + (a queue storing nodes posn)

---------------------

---------------------------------------------------------------------------------------------------------------------------

4. Path with min effort-⭐

time: O(ElogV)

Approach:

- we need to move greedily across the grid & explore path with min difference first

- hence use dijkstra with a dist matrix and a pq storing elements as { diff, posn of node }

- dist[i][j] indicates effort required to reach mat[i][j] from src through this path
- effort means max difference b/w 2 consecutive cells in that route

------------------------------------------------

----------------------------------------------------------------------------------------------------------------------------

5. Cheapest Flights within K stops-⭐

we want route with: (max K stops & min total cost)

----------------------------------------------
# Approach-1
Since we want only upto K stops or nodes to be included, so we can traverse layer by layer using BFS

- use a queue storing elements as { stops, node, dist }

- use a cost array, where cost[i] means min cost to reach this node

- when, the stops at a curr node becomes k, we check if its adj node is destination or not

- Stops are 0 at src & k+1 at destination

------------------------------------------------------------
Approach-2: (Using bellman ford)

bellman ford after i rounds guarantees to provide shortest path using at most i edges
So to reach using K stops in between it means we need at most K+1 edges
So we run bellman ford by K+1 iterations

 

-----------------------------------------------------------------------------------------------------------------------------

6. Minimum multiplications to reach from src to end-⭐

------------------------------------------------
Approach- since we need no. of steps took and at each stage we have many choices so going layer by layer would be apt so we prefer BFS here

- store elements in a queue as { product, min steps took to reach here }.
- Instead of a visited or a distance array, we use steps array to store min no. of steps for each product (since max value of end is 1e5, so take elements from 1 to 1e5 in this array) 
- While processing neighbours, we perform relaxation of steps for each

-----------------------------------------------------------------------------------------------------------------------------

7. No. of ways to arrive at a destination-⭐

Approach- Count no. of shortest paths from src to destination

Count paths with some optimal property:
Run the optimiser (here, Dijkstra) & carry a count[] array, alongside dist[],
update counts whenever you find equal-cost paths.

----------------
For example, here:

dist[v] > dist[u] + w(u,v)
1. relax edge
2. ways[v] = ways[u]

dist[v] == dist[u] + w(u,v)

1. ways[v] += ways[u]

---------------------

-----------------------------------------------------------------------------------------------------------------------------

8. Find city with smallest no. of neighbours
at a threshold distance-

Approach- Use Floyd Warshall

we need shortest distance b/w every pair of nodes (or, all pairs shortest path)
so that we can count for each node, the no. of cities which are within the threshold distance, and return smallest dist one.

---------------

1. create dist matrix using floyd warshall

2. now, for a city i, iterate over i-th row , & update cnt if, dist[i][j] <= k 

3. return min_cnt with largest index city

---------------------------------------------------------------------------------------------------------------------------