39. Graphs-5: Shortest Path

TOPICS-

1. Shortest dist in DAG (Topo)

2. Shortest dist in Undirected graph (BFS)
-----------------------------------------------------------

1. Dijkstra
2. Shortest path
3. No. of shortest paths
4. Bellmen Ford - graph with negative cycles
5. Floyd Warshall- multisource
------------------------------------------------------------

1. Shortest Path in binary matrix
2. Min Effort Path⭐
3. Cheapest Flights within K stops⭐
4. minimum multiplications
5. city with smallest no. of neighbors within threshold
-------------------------------------------------------------
1. Word Ladder-1, 2 (shortest path unweighted graphs)⭐
---------------------------------------------------------------------------------------------------------------

1. Shortest dist in a weighted DAG

TOPO + single pass relaxation

time: (N+E)

here we will get dist array at last which tells shortest dist to every node from a source node

Step-1: do a topo sort on the given graph
Step-2: relax the edges by declaring dist array with each elmt marked with INF & marking src node as 0 in dist array
Step-3: take out elements from stack & for each element & update,
total dist to reach neighbors in the dist array to
min ( new dist through curr node, existing dist of this neighbor node )

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

2. Shortest Dist in undirected graph (weight=1)

we will do by BFS

1. take a queue and a dist vector[]

2. push src node into queue

3. pop q.front and see its adj nodes and update their dist[] and if updated then push them into queue

4. repeat till queue is filled

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

3. Word Ladder-1

1. store the word list in a set

2. do BFS using queue which stores { word, counter }

3. push starting word in queue
4. pop word from queue & find all next possible words in the set, 

    if found remove them from set & insert into queue with increasing the counter

5. when you pop out last element from queue and it matches end word, return the cnt

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

4. Word Ladder-2⭐

non intuitive (thus, remember it)

(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.

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

5. Dijkstra Algo (using pq)

time: ( ElogV )

1. QUES- find shortest dist from src node to every other node

2. Intuition:- It is basically greedy BFS way of finding shortest distance but using pq instead of a queue which optimizes the order of exploration which is in turn now sorted by shortest distance so far.
3. Not for (-ve) weights based graphs, as it will fall into inf loop then...

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

1. take a min heap priority queue storing elements as{ dist, node }

2. take a dist array, assigning 0 to src node & INF to rest

3. vis adj neighbors of pq.top --> update dist array with min option --> push updated pairs into pq

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

6. Dijkstra Algo (using set)

everything is same, except a minor case where for e.g.,

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

PQ version → keep all versions, skip bad ones later
Set version → erase bad version immediately, save a few iterations

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

Dijkstra Algo (using queue)

Brute    - use queue , (this method will include storing distances of all paths)

Optimal- use priority queue, (thus, storing only shortest distances of all paths)

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

Shortest Path:

(weighted Undirected graph)

QUES- print shortest path from src to destination node

we will just do a slight modification in dijkstra , i.e., storing the parent element of every element whose dist gets updated

so for storing paths, we just need an extra parent vector...

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

Shortest Path in a Binary Matrix-

Ques- find shortest dist reqd in a binary grid, to go from top left cell to bottom right cell if u can only move through 0s
----------------------
Soln: since here, every direction takes unit dist, or all edge weights are equal (unity), so we prefer BFS instead of dijkstra 
here this question needs bfs with filtered neighbors drow, dcol wale...

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

---------------------
1. store {0, (row, col) } into queue for source node.

2. pop nodes from queue and see in all possible directions, those adj nodes which have value 0

3. update dist matrix for these adj nodes and also push them into queue
---------------------

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

Path with min effort-⭐

time: ElogV

QUES-

given a grid with each cell being effort.

find min effort to go from (0,0) to (r-1,c-1) 
if u can move in LRUD
effort in a route = max difference between 2 consecutive cells in that route

in short, we want minimum difference out of all the max differences of all paths
so we can use a min heap so we can greedily move across the grid and explore min difference path first
---------
SOLN-

dijkstra using min heap

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

---------------------------------------------------
for an adj node, check if its effort is < or > the max effort carried till its prev node,

if curr ka effort > prev ka effort => update curr ka effort to max in dist array

if curr ka effort < prev ka effort => update curr ka effort to prev waale ka max effort in dist array

Also check if dist arrray needs to be updated or not

-----------------------------------------------------
here we are relaxing edges but in a different version , like we update dist[i][j] if we get a smaller diff for it and this smaller diff is max (prev parent node tak ka effort and curr node pe aane ka effort )
--------------------------------------------------

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

Cheapest Flights within K stops-⭐

time: O(E)

here, we want:-

shortest route❌
cheapest route❌
out of all routes with max K stops , the cheapest among all✅

2 dimensions constrained Dijkstra
----------------------------------------------

WHY cost is not the focus here ?
If the priority queue only prioritizes cost, there can be situations where a path within K stops has a higher cost than another path that uses more than K stops. In such cases, cost-based prioritization alone can lead to incorrect results.

-----------------------------------------------------------------
Why simply queue can be used here instead of a priority queue ?
as here we prioritize stops and they are increasing linearly by 1
-----------------------------------------------------------------
queue prioritizing no. of stops-

1. Priority queue stores { stops, {node, dist} }
2. we use a cost array where cost[i] means min cost to reach this node⭐

2. so while traversing , then at each node we increment the stops counter & update the min cost 

3. when, the stops at a curr node becomes k, then we check if its adj node has destination or not

4. Stops are 0 at src & k+1 at destination

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

1. if  you reach destination node, no need to see for its adj node, simply continue

2. since at all levels, steps are increasing by 1 for all curr level nodes, so we can have a queue instead of priority queue, as we can always have min steps elements at q.front() too

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

Minimum multiplications to reach from src to end-

Alter- find min no. of steps to reach from src to dest (shortest dist using bfs with modified version of dist array)

--------------------------------------------
Solution-
1. we will store { prd, min no. of steps needed to reach this prd } in a queue. Also we will use steps array which contains total of 1e5 elements since end product can have value upto 1e5 , so by taking 1e5 steps array we can map no. of steps to any product using indices.
 
2. since here it is not required to go greedily like going with least product first or going with least no. of steps first so we can use bfs instead of dijkstra 

3. we will use a simple queue here, instead of min heap, since steps are increasing by 1 here.

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

count no. of shortest paths-⭐
or,
no. of ways to arrive at destination

INTUITION:- We can’t simply count how many times we reach the destination with a shortest distance, because a predecessor of the destination on a shortest path might itself be reachable in multiple different ways.

------------------------
SOLUTION-
Dijkstra along with a 'ways' array...

When dist[adjN] > dist[curn]+edgeW => 
1. relax edge
2. update the no. of ways to reach the adj node = the no. of ways to reach its parent node
3. push in queue

When dist[adjN] = dist[curn]+edgeW =>

1. then we simply increment the no. of ways to reach this adj node by 1
2. do not relax edge and do not push into queue 

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

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

Bellmen ford algo-

time: NE

1. helps to find shortest path
2. also handles negative cycles (means that sum in a cycle is <0 )

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

---------------------------
1. Relax all the edges,  (N-1) times sequentially

2. do N-1 iterations such that, in each iteration, you go through all edges (edges array can be in any order) and relax them and updating dist array.

3. After all N-1 iterations, we have final reduced distance array, which shouldn't be further reduced
4. If, it can be further reduced , we say that a negative cycle exists.

We are doing N-1 iterations, because of relaxation property of graph which states that we can have maximum of N-1 edges in the shortest path between 2 nodes in a graph

On large values of V and E, dijkstra is more optimal than bellmen ford if we just want shortest dist...

Elsewise if we want info about negative cycles, we use bellmen ford instead of dijkstra

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

Floyd Warshall Algorithm-

(all pairs shortest path algo)

1. Use:- we can tell shortest path from any src node to any destination node

2. it can also help in detecting negative cycles

3. Statement- Go via every node
4. it is kind of brute force where we are exploring all possible paths
5. It uses DP to find shortest path using Adj Matrix

     dp[i][j] means min cost to go from i to j

                                         d[i][j] = min{ d[i][k] + d[k][j], dp[i][j] } 

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

-----------------------------------------------------------------
via 1 wale matrix mein pichle via wala matrix matlab via 0 wala ki ek row aur ek col same aayega ,

ek toh 1 to x via 1 aur ek x to 1 via 1 wala , do similar for other matrices as well

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

We can also detect after the entire process that if a negative cycle exists or not-

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

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

We can also use dijkstra to find all pair shortest distance by applying dijkstra to every node which would result in N*ElogN time complexity but it won't account for negative cycles...

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

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

INTUITION- here we would need distance from each node to every other node, then we can count for each node the no. of cities which are within the threshold distance, and then return smallest wali...

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

1. use Floyd algo to create desired matrix (we can also do it by using dijkstra over every node)

2. iterate over each row (we can say we are iterating over each node), thus updating cnt for node i, whenever we find dist[i][j] <= k for node i in row i

3. at the end of row,  update min_cnt & city, if (cnt<=min_cnt)

4. Return city, if city is asked , else if no. of neighbor cities are asked, return (mincnt-1) since
cnt m[i][i]=0 bhi consider kr rha tha <=k mein

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