Hard Graphs
Shortest Path (Dijkstra)
Computes the shortest distance from node 0 to every other node in a weighted graph using Dijkstra's algorithm. Repeatedly picks the unvisited node with the smallest known distance, marks it settled, then relaxes every edge leaving it — lowering a neighbor's tentative distance whenever a shorter path is found through the current node — until every reachable node has its final, minimum distance. Receives the graph as a square adjacency matrix, where a positive value at row i, column j is the weight of an edge between nodes i and j (0 or negative means no edge; weights must be non-negative for the algorithm to be correct). Returns the shortest distance from node 0 to every node, using -1 for a node that cannot be reached at all.
Visualization
- Input
- Result
Algorithm code
// Shortest Path (Dijkstra) — a single pure function. Receives a weighted
// graph as an N×N adjacency matrix and returns the shortest distance from
// node 0 to every node, using -1 for a node that cannot be reached.
/**
* @param {number[][]} adjacencyMatrix - N×N matrix where a positive value at
* row i, column j is the weight of an edge between nodes i and j (0 or
* negative means no edge)
* @returns {number[]} shortest distance from node 0 to each node, -1 if unreachable
*/
export function shortestPath(adjacencyMatrix) {
const nodeCount = adjacencyMatrix.length;
if (nodeCount === 0) {
return [];
}
const distances = new Array(nodeCount).fill(Infinity);
const visited = new Array(nodeCount).fill(false);
distances[0] = 0;
for (let i = 0; i < nodeCount; i += 1) {
let current = -1;
let currentDistance = Infinity;
for (let node = 0; node < nodeCount; node += 1) {
if (!visited[node] && distances[node] < currentDistance) {
current = node;
currentDistance = distances[node];
}
}
if (current === -1) {
break;
}
visited[current] = true;
for (let neighbor = 0; neighbor < nodeCount; neighbor += 1) {
const weight = adjacencyMatrix[current][neighbor];
if (weight > 0 && !visited[neighbor]) {
const candidate = distances[current] + weight;
if (candidate < distances[neighbor]) {
distances[neighbor] = candidate;
}
}
}
}
return distances.map((distance) => (distance === Infinity ? -1 : distance));
}FUNCTION shortestPath(adjacencyMatrix):
nodeCount ← length(adjacencyMatrix)
IF nodeCount = 0:
RETURN empty list
distances ← array of nodeCount values, all Infinity
visited ← array of nodeCount false values
distances[0] ← 0
FOR i FROM 0 TO nodeCount - 1:
current ← -1
currentDistance ← Infinity
FOR node FROM 0 TO nodeCount - 1:
IF NOT visited[node] AND distances[node] < currentDistance:
current ← node
currentDistance ← distances[node]
IF current = -1:
BREAK
visited[current] ← true
FOR neighbor FROM 0 TO nodeCount - 1:
weight ← adjacencyMatrix[current][neighbor]
IF weight > 0 AND NOT visited[neighbor]:
candidate ← distances[current] + weight
IF candidate < distances[neighbor]:
distances[neighbor] ← candidate
RETURN distances with every Infinity replaced by -1