One Of The Hottest Algorithms in Graph Exploring Dijkstra’s Algorithm with Speedy Caching Techniques

Home stuff's

Introduction:

• Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph which represents for example our road transportation networks.
• The algorithm exists in many variants Dijkstra’s original algorithm found the shortest path between two given nodes but a more common variant fixes a single node as the “SOURCE” node and finds the shortest paths from the source to all other nodes in the graph, producing a shortest path.

What We Are Going To Learn From In Dijkstra Algo:

1. Priority Queue: Used to efficiently retrieve the vertex with the minimum distance.
2. Adjacency List: A data structure representing the graph’s edges and their weights.
3. Distance Array: Keeps track of the shortest distance from the source vertex to each vertex in the graph.
4. Visited Set: Tracks in which vertices have been visited during the algorithm’s execution.
5. Relaxation: The process of updating the distance array with shorter paths when a shorter path is found.
6. Source Vertex: The starting point from which shortest paths are calculated.
7. Target Vertex: The destination vertex for which the shortest path is being determined.
8. Edge Weight: The numerical value assigned to each edge in the graph, representing the cost of traversal.

Question Decoding:

• You just assume given a weighted undirected graph with adjList it’s an important term in our recent blogs they are just given an edge we made the adjList with according to questions but here small 🤏 change they all handed to us full adjList how good is it soooper dooper convenient
• If you don’t know what adjList is please please go back to read our recent blogs I’ve described it in a detailed manner you will easily understand what it is I strongly recommend jumping into a deep dive into the question.
• Given a graph of vertices with an adjList in the adjList, where adjList[i](I mean index okay) is a list of lists containing two integers where the first integer of each list j denotes there is an edge between i and j, and the second integer corresponds to the weight of that edge and they mentioned source of the vertex as well.
• For example [ [ [1,9],[0,9] ] ] the italic style square bracket considers an adjList[i](index)which means where do start inside of pairs the first index denoting there is an edge the second index denoting particular edge weight okay in simple manner 0 connected with 1 the edge weight is 9 and 1 connected with 0 the edge weight is 9 don’t confuse it’s an undirected weighted graph simple and the source node is 0
• One more note is the entire graph doesn’t contain any negative vertex

Visual Question Decoding:

Undirected weighted graph representation with a real-world example

Bonus for interview:

Hey, one question you might face during the interview hey candidate can you tell me what is Dijkstra in a simple explanation?

Dijkstra’s algorithm is like finding the shortest route to multiple destinations on a map Imagine you’re at a starting point and want to reach all other places in the city using the shortest paths possible You’d start by looking at nearby locations and figuring out the shortest path to each one Then you’d move to the closest location and repeat the process updating the distances to other locations as you go By doing this you gradually build up a map of the shortest paths from your starting point to every other location in the city That’s essentially what Dijkstra’s algorithm does for graphs🚗🚗🚗

Jumping into the Approaching:

We can implement Dijkstra in two ways one is SET() and another one PRIORITY QUEUE() to keep track of the nodes

• Using a Set: In Dijkstra, we are going to approach with a set, you can keep track of visited nodes and their distances. This approach works well for graphs with small numbers of nodes or when the graph has a limited range of distances between nodes in the next blog will see with PQ one important in JS doesn’t have any inbuilt PQ but we can make it let’s see.
• Using a Priority Queue: A priority queue is more efficient for larger graphs or graphs with varying distances between nodes It allows you to efficiently retrieve the node with the shortest distance to the starting node, making it suitable for Dijkstra’s algorithm
• One more thing Both implementations give the same result but the choice between them depends on factors such as the size and characteristics of the graph you’re working with 👍

As I told you before we are going to use Set()DS for monitoring visited node then one more Distance Array and some usual stuff all enough with the help of stuff we are going to crack Dijkstra I’ll try to explain through visually because you don’t want to read 1000 lines just one picture make sense to explain very well manner trust me guys…

Dijkstra Visual Dry-Run with Core:

Don’t be afraid of seeing this picture just see the Roman Numerals they will tell you what’s the first and second, please move one by one i 200% sure this will make sense what’s the core and the dry-run of the Dijkstra you don’t want to read 1000 or 2000 lines just one picture enough to understand Dijkstra if this picture helps you don’t forget to hit follow button

Where to Start to End:

👉 First, create a Set() for monitoring visited nodes they are given total nodes with the total nodes and create a distance array filled with Infinite we need a minimum value that’s why we choose Infinite or you can choose Min. value something.
👉 How do we store all the nodes and dist in Set() we need to store all the nodes and distance of the edge as a pair which means [distance, currNode] so one thing they are given source node we always start with source node.
👉 Here starting with [0, 0] 1st index distance 2nd index current node as I told you before we need to onboard with the pair of the source node don’t forget to fill with this distance to distance array during the algorithm process just fill with distance[source] = 0 the source can be anything.

Question: how do you put source node distance 0? just simply when you’re starting to find the shortest paths from a specific node (the source node), you mark its distance as 0 because it’s already at that node and doesn’t need to travel any distance to reach itself. So, in a nutshell, to make the source node’s distance 0, you just assign the value 0 to its distance variable

👉 Next run a while loop till Set() becomes empty which means Set().size!== 0 there is a heart of the problem first and most first extract the node and dist from the Set() in JS has one method (.next) everything at stored as an array let’s destructure the nodes and distance or stored at separate variable “Don’t forget to write reasonable variable names” afterwards don’t forget to delete the extracted node from the set() because refuse unnecessary execution…
👉 Then you all know that finding the who is “Adjacent” to the extracted nodes means the current Node from this loop will get the adjacent node then we need to figure out the distance from the current Node to the adjacent Node if the figured distance is better then previous we can blindly go with that.

Question: How do we figure out the Marudhu distance from the current Node to the adjacent Node 👇?

      for (let neighbor of adj[node]) {
        // console.log(neighbor, "neighbor before extract");
        let neighNode = neighbor[0];
        let neighWeight = neighbor[1];
        // 1 3
        // 0 6
        // console.log(neighNode, neighWeight);
// dist means current distance + neighWeight < distance[neightNode] that means 
// i've already told you in starting making distance array in this case 
// 0 is source node from the first loop adjacenet node 0 is 1 we need to fill 
// with distance[1] array this is is the shortest distance from 0 in future you may get
// better distance if it is better you can fill with new distance doesn't matter
        if (dist + neighWeight < distance[neighNode]) {
// in mid of the time you can get better distance that previous one that time 
// you don't want to processing the node you can simply delete from the set()
// you can get better time Complexity refuse unnecessory calculation.....
          if (distance[neighNode] != Infinity) {
            // simply deleted node from the stack because not need to do repetetive sum that's why
            setDs.delete([distance[neighNode], neighNode]);
          }
// if it is better then previous one just push into the set() data structure
// i've already told you until set() becomes empty.......
          distance[neighNode] = dist + neighWeight;
          setDs.add([distance[neighNode], neighNode]);
        }
      }

Code Showcase:

class Solution {
  dijkstra(V, adj, S) {
    let setDs = new Set();
    let distance = new Array(V).fill(Infinity);
// source node distance always 0 along with fill distance array...
    distance[S] = 0;

    setDs.add([0, S]);

    while (setDs.size !== 0) {
      let extraction = setDs.values().next().value;
      // console.log(extraction, "while extraction");
      let node = extraction[1];
      let dist = extraction[0];
// don't forget.....
      setDs.delete(extraction);

      for (let neighbor of adj[node]) {
        // console.log(neighbor, "neighbor before extract");
        let neighNode = neighbor[0];
        let neighWeight = neighbor[1];
        // 1 3
        // 0 6
        // console.log(neighNode, neighWeight);
        if (dist + neighWeight < distance[neighNode]) {
          if (distance[neighNode] != Infinity) {
            // simply deleted node from the stack because not need to do repetetive sum that's why
            setDs.delete([distance[neighNode], neighNode]);
          }

          distance[neighNode] = dist + neighWeight;
          setDs.add([distance[neighNode], neighNode]);
        }
      }
    }

    return distance;
  }
}

let totalVertex = 3;
let source = 2;
let adjList = [
  [
    [1, 1],
    [2, 6],
  ],
  [
    [2, 3],
    [0, 1],
  ],
  [
    [1, 3],
    [0, 6],
  ],
];

let data = new Solution();
let output = data.dijkstra(totalVertex, adjList, source);
console.log(output, "this you shortest path in dj algo");

Why should I learn Dijkstra👇:

Dijkstra’s algorithm is a fundamental tool in graph theory and has wide-ranging applications in various fields such as computer networking, transportation systems, and route planning. By efficiently finding the shortest paths from a source node to all other nodes in a graph, it helps optimize resource allocation, minimize travel time, and improve overall system performance. Understanding Dijkstra’s algorithm is essential for tackling complex optimization problems and designing efficient algorithms for real-world scenarios.

Time to Say Bye-Bye🙌:

From this blog, I hope you will get something thanks for sticking so far If you read these lines you might get some leads about Dijkstra's solid principles and how it works behind the code you may heard a lot of time from others Dijkstra, Dijkstra, Dijkstra sometimes you will scared about Dijkstra but I hope not anymore this one might smashed everything about scaring okay don’t want to make frustrate again If you really enjoyed the content, please consider following me and hitting the applaud button Bye-bye let’s see ya at the next blog…🙌