Implement Dijkstra's Algorithm for Shortest Paths

Dijkstra's algorithm is a fundamental graph traversal algorithm used to find the shortest paths from a single source vertex to all other vertices in a graph with non-negative edge weights. This is a crucial algorithm in many applications, including network routing, GPS navigation, and resource allocation. Your task is to implement this algorithm in JavaScript.

Problem Description

You are tasked with creating a JavaScript function that implements Dijkstra's algorithm. This function will take a graph represented as an adjacency list and a starting node as input. It should return an object containing the shortest distance from the start node to every other node in the graph, and the preceding node in the shortest path to reconstruct the path itself.

Key Requirements:

• Graph Representation: The graph will be provided as an adjacency list. Each key in the object will represent a node, and its value will be an array of objects. Each object in the array will represent an edge, with properties node (the destination node) and weight (the cost of the edge).
• Shortest Distances: The function must calculate the shortest distance from the startNode to all reachable nodes in the graph.
• Path Predecessors: For each node, you need to store the node that immediately precedes it on the shortest path from the startNode. This will allow for path reconstruction.
• Unreachable Nodes: If a node is unreachable from the startNode, its distance should be considered infinity.

Expected Behavior:

The function should return an object with two keys:

• distances: An object where keys are node names and values are the shortest distances from the startNode.
• predecessors: An object where keys are node names and values are the preceding node on the shortest path from the startNode.

Edge Cases to Consider:

• Empty Graph: The input graph might be empty.
• Single Node Graph: The graph might contain only the start node.
• Disconnected Graph: Some nodes might not be reachable from the start node.
• Start Node Not in Graph: The provided startNode might not exist in the graph.

Examples

Example 1:

Input:
graph = {
  'A': [{ node: 'B', weight: 4 }, { node: 'C', weight: 2 }],
  'B': [{ node: 'A', weight: 4 }, { node: 'E', weight: 3 }],
  'C': [{ node: 'A', weight: 2 }, { node: 'D', weight: 2 }, { node: 'F', weight: 4 }],
  'D': [{ node: 'C', weight: 2 }, { node: 'E', weight: 3 }],
  'E': [{ node: 'B', weight: 3 }, { node: 'D', weight: 3 }, { node: 'F', weight: 1 }],
  'F': [{ node: 'C', weight: 4 }, { node: 'E', weight: 1 }]
}
startNode = 'A'

Output:
{
  distances: { A: 0, B: 4, C: 2, D: 4, E: 7, F: 6 },
  predecessors: { A: null, B: 'A', C: 'A', D: 'C', E: 'F', F: 'E' }
}

Explanation:
The shortest distance from 'A' to 'A' is 0.
The shortest distance from 'A' to 'B' is 4 (A -> B).
The shortest distance from 'A' to 'C' is 2 (A -> C).
The shortest distance from 'A' to 'D' is 4 (A -> C -> D).
The shortest distance from 'A' to 'E' is 7 (A -> C -> F -> E).
The shortest distance from 'A' to 'F' is 6 (A -> C -> F).
The predecessor for 'E' is 'F' because the path A -> C -> F -> E is shorter than A -> B -> E.

Example 2:

Input:
graph = {
  'X': [{ node: 'Y', weight: 1 }],
  'Y': [{ node: 'Z', weight: 5 }],
  'Z': []
}
startNode = 'X'

Output:
{
  distances: { X: 0, Y: 1, Z: 6 },
  predecessors: { X: null, Y: 'X', Z: 'Y' }
}

Explanation:
The shortest path from 'X' to 'Y' is X -> Y with distance 1.
The shortest path from 'X' to 'Z' is X -> Y -> Z with distance 1 + 5 = 6.

Example 3: (Disconnected Graph)

Input:
graph = {
  'P': [{ node: 'Q', weight: 3 }],
  'Q': [{ node: 'P', weight: 3 }],
  'R': [{ node: 'S', weight: 1 }],
  'S': [{ node: 'R', weight: 1 }]
}
startNode = 'P'

Output:
{
  distances: { P: 0, Q: 3, R: Infinity, S: Infinity },
  predecessors: { P: null, Q: 'P', R: null, S: null }
}

Explanation:
Nodes 'R' and 'S' are in a separate component and are unreachable from 'P'.

Constraints

• The graph can contain up to 1000 nodes and 2000 edges.
• Node names will be strings.
• Edge weights will be positive integers (greater than 0).
• The input graph will be a JavaScript object representing an adjacency list.
• The startNode will be a string.
• The algorithm should have a time complexity suitable for the given constraints (e.g., O(E log V) or O(V^2) where V is the number of vertices and E is the number of edges).

Notes

• You will need a way to efficiently select the node with the smallest distance that hasn't been visited yet. A priority queue is a common and efficient data structure for this. However, you can also implement a simpler version using an array and sorting/searching if a full priority queue implementation is too complex initially.
• Initialize all distances to infinity, except for the start node, which should have a distance of 0.
• Remember to handle the case where the startNode is not present in the graph.
• The predecessors object will help in reconstructing the actual shortest path if needed, though the primary output is the distances. You can set the predecessor of the startNode to null.