GAZAR

Principal Engineer | Mentor
Dijkstra's Algorithm

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.

Comments