djikstra

Djikstra

A TypeScript implementation of Dijkstra's algorithm for finding shortest paths in graphs.

Installation

npm install djikstra

Usage

import { findShortestPath } from 'djikstra';

const graph = {
  A: { B: 5, C: 2 },
  B: { A: 5, D: 1 },
  C: { A: 2, D: 6 },
  D: { B: 1, C: 6, E: 2 },
  E: { D: 2 },
};

const result = findShortestPath(graph, 'A', 'E');

if (result.status === 'reachable') {
  console.log(result.path);     // ['A', 'B', 'D', 'E']
  console.log(result.distance); // 8
}

Implementation

Uses a binary min-heap priority queue for O(E log V) performance. Single-target queries terminate early when the destination is reached.

Graph Format

Graphs are adjacency lists as plain objects. Edges are directional — if you want to travel both ways, add both directions:

const roadNetwork = {
  "NewYork":      { "Boston": 215, "Philadelphia": 95 },
  "Boston":       { "NewYork": 215, "Portland": 112 },
  "Philadelphia": { "NewYork": 95, "Washington": 140 },
  "Portland":     { "Boston": 112 },
  "Washington":   { "Philadelphia": 140 }
};

Each key is a node, each value maps neighbors to edge weights. Weights can differ by direction (e.g. uphill vs downhill).

Errors

The library throws on invalid input rather than returning silently wrong results:

Condition	Error
Source node not in graph	Source node "X" does not exist in the graph.
Destination node not in graph (not even as a neighbor)	Destination node "X" does not exist in the graph.
Negative, NaN, or Infinity edge weight	Invalid edge weight ... Weights must be finite and non-negative.

If source and destination are valid but no path exists, findShortestPath returns { status: 'unreachable' } instead of throwing.

API Reference

findShortestPath

findShortestPath(graph: Graph, source: string, destination: string): PathResult

Calculates the shortest path between two nodes in a graph.

Parameter	Type	Description
graph	Graph	The graph represented as an adjacency list
source	string	The starting node ID
destination	string	The target node ID

Returns: A discriminated union with either reachable or unreachable status

type PathResult = 
  | { status: 'reachable'; path: string[]; distance: number }
  | { status: 'unreachable' }

Throws: See Errors

computeAllPaths

computeAllPaths(graph: Graph, source: string): Record<string, number>

Computes the shortest distance from a source to all nodes in the graph, including Infinity for unreachable ones.

Parameter	Type	Description
graph	Graph	The graph represented as an adjacency list
source	string	The starting node ID

Returns: An object mapping each node ID to its shortest distance from the source (Infinity for unreachable nodes)

computeDistancesAndPaths

computeDistancesAndPaths(
  graph: Graph, 
  source: string
): { 
  distances: Record<string, number>; 
  predecessors: Record<string, string> 
}

Provides complete pathfinding information from a source to all nodes.

Parameter	Type	Description
graph	Graph	The graph represented as an adjacency list
source	string	The starting node ID

Returns:

• distances: Maps each node ID to its shortest distance from source
• predecessors: Maps each node ID to its predecessor in the shortest path

Note: Use the predecessors map to reconstruct the full path to any node

License

ISC