GAZAR

Principal Engineer | Mentor

Dijkstra's Algorithm

Dijkstra's Algorithm

Let's talk about Dijkstra's Algorithm. It's this super cool thing in computer science that helps us find the shortest path between two points in a graph. Sounds fancy, right? Well, it is, but don't worry, I'll break it down for you.

So, imagine you have this maze of nodes and connections. Each connection has a distance associated with it. Dijkstra's Algorithm helps us navigate through this maze and find the shortest path from one node to another.

Here's how it works:

  • Start at the Source: You pick a starting point, let's call it the source node.
  • Explore Nearby Nodes: Look at all the nodes connected to the source and calculate the distance from the source to each one.
  • Choose the Shortest Path: Pick the node with the shortest distance from the source. This becomes your current node.
  • Repeat: Keep repeating steps 2 and 3, but now from your current node. Keep track of the shortest distance to each node as you go along.
  • Destination Reached: Once you reach your destination node, you've found the shortest path!

Now, let's see some JavaScript in action. Here's a basic implementation of Dijkstra's Algorithm:

const graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'A': 4, 'D': 5},
    'C': {'A': 2, 'D': 7},
    'D': {'B': 5, 'C': 7}
};

const dijkstra = (myGraph, source) => {
    const distances = {};
    const visited = {};
    const queue = [{ node: source, distance: 0 }]
  
    while (queue.length > 0){
        queue.sort((a,b) => a.distance - b.distance);
        const { node, distance } = queue.shift();
        if (!visited[node]) {
            visited[node] = true;
            distances[node] = distance;
            Object.keys(graph[node]).map((secondNode) => {
                queue.push({
                    node: secondNode,
                    distance: graph[node][secondNode] + distances[node] || 0
                })
            })
        }
    }
    return distances;
}

console.log(dijkstra(graph, 'A'))

Pretty cool, right? With just a few lines of code, we can find the shortest path through a maze of nodes and connections.