Finding the Shortest Path with Dijkstra's Algorithm

Dijkstra's algorithm is a classic graph search algorithm used to find the shortest paths from a starting node to all other nodes in a graph. This challenge asks you to implement Dijkstra's algorithm in JavaScript, allowing you to demonstrate your understanding of graph traversal and optimization techniques. It's a fundamental algorithm in computer science with applications in routing, network optimization, and more.

Problem Description

You are tasked with implementing Dijkstra's algorithm to find the shortest paths from a source node to all other nodes in a weighted graph. The graph will be represented as an adjacency list, where each key in the list represents a node, and the value is an array of objects. Each object in the array represents an edge connecting the node to another node, with properties node (the destination node) and weight (the cost of traversing that edge).

What needs to be achieved:

• Implement a function dijkstra(graph, source) that takes a graph (adjacency list) and a source node as input.
• The function should return an object where the keys are the nodes in the graph and the values are the shortest distances from the source node to each node. If a node is unreachable from the source, its distance should be Infinity.

Key Requirements:

• The algorithm must correctly calculate the shortest distances from the source node to all other nodes.
• The algorithm should handle graphs with positive edge weights only.
• The algorithm should efficiently explore the graph to find the shortest paths.

Expected Behavior:

The dijkstra function should return an object representing the shortest distances from the source node. The keys of the object should be the nodes in the graph, and the values should be the shortest distances.

Edge Cases to Consider:

• Empty Graph: Handle the case where the input graph is empty.
• Source Node Not in Graph: Handle the case where the source node is not present in the graph.
• Disconnected Graph: Handle cases where some nodes are unreachable from the source node.
• Negative Edge Weights: Dijkstra's algorithm does not work with negative edge weights. While you don't need to explicitly check for them, be aware of this limitation.

Examples

Example 1:

Input:
graph = {
  'A': [{ node: 'B', weight: 4 }, { node: 'C', weight: 2 }],
  'B': [{ node: 'D', weight: 5 }],
  'C': [{ node: 'B', weight: 1 }, { node: 'D', weight: 8 }],
  'D': []
};
source = 'A';

Output:
{
  'A': 0,
  'B': 3,
  'C': 2,
  'D': 8
}

Explanation:
The shortest path from 'A' to 'B' is A -> C -> B (2 + 1 = 3).
The shortest path from 'A' to 'C' is A -> C (2).
The shortest path from 'A' to 'D' is A -> C -> B -> D (2 + 1 + 5 = 8).

Example 2:

Input:
graph = {
  'A': [{ node: 'B', weight: 10 }, { node: 'C', weight: 3 }],
  'B': [],
  'C': [{ node: 'B', weight: 1 }]
};
source = 'A';

Output:
{
  'A': 0,
  'B': 4,
  'C': 3
}

Explanation:
The shortest path from 'A' to 'B' is A -> C -> B (3 + 1 = 4).
The shortest path from 'A' to 'C' is A -> C (3).

Example 3: (Disconnected Graph)

Input:
graph = {
  'A': [{ node: 'B', weight: 1 }],
  'B': [],
  'C': []
};
source = 'A';

Output:
{
  'A': 0,
  'B': 1,
  'C': Infinity
}

Explanation:
Node 'C' is not reachable from 'A', so its distance is Infinity.

Constraints

• The graph will be represented as an adjacency list (object).
• Node names will be strings.
• Edge weights will be non-negative numbers.
• The number of nodes in the graph will be between 1 and 100.
• The number of edges in the graph will be between 0 and 500.
• The algorithm should have a time complexity of O(V^2) or better, where V is the number of vertices (nodes) in the graph. Using a priority queue (e.g., a min-heap) can achieve O(E log V) time complexity, which is more efficient for larger graphs.

Notes

• You can use any standard JavaScript data structures and methods.
• Consider using a priority queue (min-heap) to efficiently select the node with the smallest distance to explore next. This will significantly improve performance for larger graphs.
• Initialize the distances to all nodes as Infinity except for the source node, which should be initialized to 0.
• Keep track of visited nodes to avoid cycles and redundant calculations.
• The algorithm iteratively explores the graph, updating the shortest distances to each node as it finds shorter paths.