Two-way road graph finding the shortest path in an undirected graph having *unit distance* with edges

Just mixing up everything in one place the picture will let us know what we are going to learn from this blog

Not a disclaimer just read it at once before jumping into the problem in the last blog we did a directed graph shortest path which means one-way but here two-way path which means assume 1 — — → 2 this one directed graph you can only move 1 to 2 you never go back to 2 to 1 but this one UNDIRECTED graph so you can move 1 to 2 and 2 to 1 as well.

Introduction:

In this blog, we are going to find the shortest path undirected graph which means you can reach both nodes (*in a directed graph you have a direction so you just move onto the direction you can’t revert back to where you started if you want to come to where do start that only possible with the help of some other nodes*) before jumping into the problem If you haven’t check it out our last blog please please eyes at once I strongly recommended because we’ve solved the directed graph shortest path problem with deep visual and pseudo code as well so don’t want to waste our time let’s jump into the problem.👇

Question Decoding:

• First, we will decode the question and then see what the best approach for this particular shortest path problem is:
• The question strictly says all the edges have unit distance which means assuming all the edges have the same amount of weights all all all so it is easy to solve this problem but one question might arise if all the edges have the same weights how will the unit distance affect into the distance one from other vertexes let’s see you might wonder hahaha.
• Find the shortest path from src to all the vertex and if it is unreachable to reach any vertex, then return -1 for that vertex as we did in the last problem it still has some vertex unreachable just return -1 if you don’t how it works please go back to read our last blog you will understand what’s going on behind the scenes that’s all the question states.
• In this problem, they are just given the edges for all the nodes they never mention the weight of the edges instead of adding the weights with the list of edges they mentioned at the top of the question all the edges have unit distance okay when comes to edges we want to make adjList it’s one of the graph representation then make some process with the adjList find the shortest path.

Visual Question Decoding:

question decoding visually if you are laze person to read the paragraph just eyes at once the image you will understand what the question states

Approaching Problem:

In the upcoming problem, we are going to try different algorithms to find the shortest path like Dijkstra and Floyd Warshall some new algorithms but now we are going to approach with simple BFS techniques if you don’t know about BFS go back and read my LinkedIn post I delivered crystal clear explanation with deep visual just wait I’ll drop the link along with the line BFS Linkedin Post you might wonder how BFS will help you to find shortest distance each node to every other node just wail will together to demonstrate the myth

• Note: first and mostly as I told you in the last blog before jumping into the core problem If the question gives an edges list, we want to make an adjList with the edges and then apply BFS to find the shortest path when comes to BFS first comes to your mind Queue (Q) yes FiFo who comes first into the Q the one processed first that’s the core of FIFO okay fine let’s move towards to the core.
• Making adjList with the edges In the last blog we saw how to make adjList along with the weight of the edges now we don’t have any weights in the list of edges so easy to make the adjList just push the adjNode A to B at the moment we should push B to A because this one undirected graph so the both node can reach each other node

Let’s see how to make adjList:

Making adjList If you don’t know what the adjList is one of the ways to represent graph data structure

Let’s apply BFS to the undirected graph:

If you don’t know about BFS there are two to traverse the graph 1) DFS is a DEPTH via traverse keep digging 2) BFS is a LEVEL via traversal okay after making an adjList list create a distance array filled with the infinite length of the adjList array then they had mentioned what’s the source node so the source node distance always 0 just push into the queue in this problem 0 is the source node so distance[src] which means distance[0] = 0 fill with the distance array thereby we have one node in the queue just extract the node from the Q then run a loop who has an adjacent node of 0 if anyone has just calculate the distance if the distance is better then previous one just put into the distance array to that particular node we should do untill queue became 0 if you have still confusion just wait will see in visually how will this works I’ve discovered every dry run into one picture you can easily understood what’s happens in behind the scenes I’m really put a heavy effort to make this so don’t forget to mention follow if you’d any doubt created on the picture just drop a command I’ll sort it out.

Full DryRun Don’t Afraid:

If you are preparing for the interview you might not have much time to read all the lines so in this one also who are preparing interview you just see the picture at once you will understand this one picture more more enough to understood what’s core and what’s behind the scenes trust me guys

A full dry run of the entire problem this one more enough to understand the surprising things inside the problem

Code ShowCase:

class Solution {
  shortest(n, m, edges, src) {
/// fist and most make adjList with the edges
    let adj = new Array(n).fill(null).map(() => []);

    for (let adjacent of edges) {
      adj[adjacent[0]].push(adjacent[1]);
      adj[adjacent[1]].push(adjacent[0]);
    }
    console.log(adj, "your adj List");

    let distance = new Array(n).fill(1e9);
    // why so we make 0 with src because the questions strictly says we go from the src to all node's that's we first push into the queue simple don't chaos read the question
    distance[src] = 0;
    let queue = [];
    queue.push(src);
// we should run a loop untill Q became 0 that's what it is.
    while (queue.length > 0) {
      let node = queue.shift();
      console.log(node, "this is node ");
      for (let neighbor of adj[node]) {
        // +1 means all the edges has unit distance or weights you can assume
        // if you current distance is better then previous one just filled out
        if (distance[node] + 1 < distance[neighbor]) {
          distance[neighbor] = 1 + distance[node];
// don't forget to push the neighbor that's the core of bfs level wise traversal
          queue.push(neighbor);
        }
      }
    }
    // if it is unreachable to reach any vertex, then return -1 for that vertex that's the loop
    let ans = new Array(n).fill(-1);
    for (let i = 0; i < n; i++) {
      if (distance[i] != 1e9) {
        ans[i] = distance[i];
      }
    }
    return ans;
  }
}

let edges = [
  [0, 1],
  [0, 3],
  [3, 4],
  [4, 5],
  [5, 6],
  [1, 2],
  [2, 6],
  [6, 7],
  [7, 8],
  [6, 8],
];

let n = 9;
let m = 10;
let src = 0;

let data = new Solution();
let output = data.shortest(n, m, edges, src);
console.log(output, "this one is yours");

Time to say bye-bye:

I’m always grateful to each and everyone who supported me with your likes and commands thanks for sticking together so far If you are in the bye-bye section you really well know what’s the question trying to say I hope I’ve tried to explain it clearly for everyone if you have still wanted to know more about this one just drop a command I’ll sort it out If you really enjoyed the content please please consider following me and hitting the applaud button bye-bye let’s see ya at next blog.