🚀 Big News:Socket Has Acquired Secure Annex.Learn More →
Socket
Book a DemoSign in
Socket
Book a DemoSign in

djikstra

Package Overview
Dependencies
Maintainers
1
Versions
2
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

djikstra - npm Package Compare versions

Comparing version
0.1.1
 to
0.2.0
+22
dist/djisktra.d.ts
interface GraphNode {
[neighbor: string]: number;
}
interface Graph {
[node: string]: GraphNode;
}
interface ReachableResult {
status: 'reachable';
path: string[];
distance: number;
}
interface UnreachableResult {
status: 'unreachable';
}
type PathResult = ReachableResult | UnreachableResult;
export declare function findShortestPath(graph: Graph, source: string, destination: string): PathResult;
export declare function computeAllPaths(graph: Graph, source: string): Record<string, number>;
export declare function computeDistancesAndPaths(graph: Graph, source: string): {
distances: Record<string, number>;
predecessors: Record<string, string>;
};
export type { Graph, GraphNode, PathResult, ReachableResult, UnreachableResult };
+85
dist/djisktra.js
import { MinHeap } from './minHeap.js';
function validateGraph(graph, source, destination) {
if (!graph[source]) {
throw new Error(`Source node "${source}" does not exist in the graph.`);
}
let foundDestination = destination === undefined || destination in graph;
for (const node in graph) {
for (const neighbor in graph[node]) {
const weight = graph[node][neighbor];
if (!Number.isFinite(weight) || weight < 0) {
throw new Error(`Invalid edge weight ${weight} on edge ${node} -> ${neighbor}. Weights must be finite and non-negative.`);
}
if (!foundDestination && neighbor === destination) {
foundDestination = true;
}
}
}
if (!foundDestination) {
throw new Error(`Destination node "${destination}" does not exist in the graph.`);
}
}
function runDijkstra(graph, source, earlyStop) {
const distances = {};
const predecessors = {};
const visited = new Set();
for (const node in graph) {
distances[node] = node === source ? 0 : Infinity;
}
const queue = new MinHeap((a, b) => a.distance - b.distance);
queue.push({ node: source, distance: 0 });
while (!queue.isEmpty()) {
const current = queue.pop();
if (!current)
break;
const { node: currentNode, distance: currentDistance } = current;
if (visited.has(currentNode) || currentDistance > distances[currentNode]) {
continue;
}
visited.add(currentNode);
if (earlyStop !== undefined && currentNode === earlyStop) {
break;
}
const neighbors = graph[currentNode] || {};
for (const neighbor in neighbors) {
if (visited.has(neighbor))
continue;
const edgeWeight = neighbors[neighbor];
const totalDistance = currentDistance + edgeWeight;
if (totalDistance < (distances[neighbor] ?? Infinity)) {
distances[neighbor] = totalDistance;
predecessors[neighbor] = currentNode;
queue.push({ node: neighbor, distance: totalDistance });
}
}
}
return { distances, predecessors };
}
function reconstructPath(predecessors, destination) {
const path = [destination];
let current = destination;
while (predecessors[current]) {
current = predecessors[current];
path.push(current);
}
return path.reverse();
}
export function findShortestPath(graph, source, destination) {
validateGraph(graph, source, destination);
const { distances, predecessors } = runDijkstra(graph, source, destination);
if (distances[destination] === undefined || distances[destination] === Infinity) {
return { status: 'unreachable' };
}
return {
status: 'reachable',
path: reconstructPath(predecessors, destination),
distance: distances[destination],
};
}
export function computeAllPaths(graph, source) {
return computeDistancesAndPaths(graph, source).distances;
}
export function computeDistancesAndPaths(graph, source) {
validateGraph(graph, source);
return runDijkstra(graph, source);
}
+2
dist/index.d.ts
export { findShortestPath, computeAllPaths, computeDistancesAndPaths } from './djisktra.js';
export type { Graph, GraphNode, PathResult, ReachableResult, UnreachableResult } from './djisktra.js';
+1
dist/index.js
export { findShortestPath, computeAllPaths, computeDistancesAndPaths } from './djisktra.js';
+12
dist/minHeap.d.ts
export declare class MinHeap<T> {
private data;
private compare;
constructor(compareFn: (a: T, b: T) => number);
push(item: T): void;
pop(): T | undefined;
peek(): T | undefined;
size(): number;
isEmpty(): boolean;
private bubbleUp;
private bubbleDown;
}
+59
dist/minHeap.js
export class MinHeap {
constructor(compareFn) {
this.data = [];
this.compare = compareFn;
}
push(item) {
this.data.push(item);
this.bubbleUp(this.data.length - 1);
}
pop() {
if (this.data.length === 0)
return undefined;
const top = this.data[0];
const bottom = this.data.pop();
if (this.data.length > 0 && bottom !== undefined) {
this.data[0] = bottom;
this.bubbleDown(0);
}
return top;
}
peek() {
return this.data[0];
}
size() {
return this.data.length;
}
isEmpty() {
return this.data.length === 0;
}
bubbleUp(index) {
const item = this.data[index];
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.compare(item, this.data[parentIndex]) >= 0)
break;
this.data[index] = this.data[parentIndex];
index = parentIndex;
}
this.data[index] = item;
}
bubbleDown(index) {
const length = this.data.length;
const item = this.data[index];
while (true) {
const leftChild = 2 * index + 1;
if (leftChild >= length)
break;
const rightChild = 2 * index + 2;
const smallest = rightChild < length && this.compare(this.data[rightChild], this.data[leftChild]) < 0
? rightChild
: leftChild;
if (this.compare(item, this.data[smallest]) <= 0)
break;
this.data[index] = this.data[smallest];
index = smallest;
}
this.data[index] = item;
}
}
+11
-27
package.json
{
"name": "djikstra",
"version": "0.1.1",
"version": "0.2.0",
"description": "A TypeScript implementation of Dijkstra's algorithm for finding shortest paths in graphs",

@@ -26,15 +26,8 @@ "keywords": [

".": {
"import": {
"types": "./dist/esm/index.d.ts",
"default": "./dist/esm/index.js"
},
"require": {
"types": "./dist/commonjs/index.d.ts",
"default": "./dist/commonjs/index.js"
}
"types": "./dist/index.d.ts",
"default": "./dist/index.js"
}
},
"main": "./dist/commonjs/index.js",
"module": "./dist/esm/index.js",
"types": "./dist/commonjs/index.d.ts",
"main": "./dist/index.js",
"types": "./dist/index.d.ts",
"files": [

@@ -47,29 +40,20 @@ "dist",

"format": "prettier --write .",
"build": "tshy",
"clean": "tshy clean",
"build": "tsc",
"clean": "rm -rf dist",
"test": "vitest run",
"test:watch": "vitest",
"test:coverage": "vitest run --coverage",
"prepublishOnly": "npm run build"
"prepublishOnly": "npm run build",
"postpublish": "npm logout"
},
"tshy": {
"exports": {
".": "./src/index.ts"
},
"formats": {
"esm": true,
"commonjs": true
}
},
"devDependencies": {
"@typescript-eslint/eslint-plugin": "^8.27.0",
"@typescript-eslint/parser": "^8.27.0",
"@vitest/coverage-v8": "^3.0.9",
"@vitest/coverage-v8": "^4.1.2",
"eslint": "^9.23.0",
"eslint-config-prettier": "^10.1.1",
"prettier": "^3.5.3",
"tshy": "^3.0.2",
"typescript": "^5.8.2",
"vitest": "^3.0.9"
"vitest": "^4.1.2"
}
}
+28
-88
README.md

@@ -7,3 +7,2 @@ # Djikstra

![Tests](https://github.com/jonchurch/djikstra/workflows/Tests/badge.svg)
![Coverage](https://img.shields.io/codecov/c/github/jonchurch/djikstra)

@@ -19,5 +18,4 @@ ## Installation

```typescript
import Djikstra from 'djikstra';
import { findShortestPath } from 'djikstra';
// Create a graph as an adjacency list
const graph = {

@@ -31,102 +29,44 @@ A: { B: 5, C: 2 },

const pathfinder = new Djikstra();
const result = findShortestPath(graph, 'A', 'E');
// Find shortest path between two nodes
const result = pathfinder.findShortestPath(graph, 'A', 'E');
if (result.status === 'reachable') {
console.log(`Path found: ${result.path.join(' → ')}`);
console.log(`Total distance: ${result.distance}`);
} else {
console.log('No path exists to the destination');
console.log(result.path); // ['A', 'B', 'D', 'E']
console.log(result.distance); // 8
}
// Compute distances to all nodes
const allDistances = pathfinder.computeAllPaths(graph, 'A');
console.log(allDistances);
// Output: { A: 0, B: 5, C: 2, D: 6, E: 8 }
// Compute both distances and paths
const fullResult = pathfinder.computeDistancesAndPaths(graph, 'A');
console.log(fullResult);
// Output: {
// distances: { A: 0, B: 5, C: 2, D: 6, E: 8 },
// predecessors: { B: 'A', C: 'A', D: 'B', E: 'D' }
// }
```
## Algorithm Implementation
## Implementation
This library implements Dijkstra's algorithm using a binary min-heap priority queue for performance optimization. Here's what you should know about our implementation:
Uses a binary min-heap priority queue for O(E log V) performance. Single-target queries terminate early when the destination is reached.
### Approach
## Graph Format
- **Standard Algorithm**: The implementation follows the classic Dijkstra's algorithm but uses modern data structures
- **Priority Queue**: Uses a binary min-heap for efficient extraction of the node with the smallest distance
- **Lazy Updates**: Implements "lazy deletion" approach that allows duplicate nodes in the queue but skips already processed ones
- **Early Termination**: Stops when the destination is reached (for single-path finding)
Graphs are adjacency lists as plain objects. **Edges are directional** — if you want to travel both ways, add both directions:
### Performance Characteristics
- **Time Complexity**: O(E log V) where V is the number of vertices and E is the number of edges
- **Space Complexity**: O(V) for storing distances, predecessors, and the priority queue
### Tradeoffs
- **Heap vs. Fibonacci Heap**: Uses a binary heap (O(log V) operations) instead of a Fibonacci heap (theoretically faster at O(1) decrease-key) for better real-world performance and implementation simplicity
- **Specialized vs. General**: Focuses on path finding rather than implementing a general-purpose graph library
- **Memory vs. Speed**: Prioritizes speed with the priority queue approach over memory efficiency
## Creating your own graph
Graphs are represented as adjacency lists using plain JavaScript objects:
```typescript
// Graph structure
interface Graph {
[node: string]: {
[neighbor: string]: number
}
}
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 in the outer object represents a node in the graph. The value is another object where:
- Keys are the IDs of neighboring nodes
- Values are the edge weights (distances) to those neighbors
Each key is a node, each value maps neighbors to edge weights. Weights can differ by direction (e.g. uphill vs downhill).
Example for a road network:
## Errors
```typescript
const roadNetwork = {
// Each city with its connections
"NewYork": {
"Boston": 215, // Distance in miles
"Philadelphia": 95
},
"Boston": {
"NewYork": 215,
"Portland": 112
},
"Philadelphia": {
"NewYork": 95,
"Washington": 140
},
"Portland": {
"Boston": 112
},
"Washington": {
"Philadelphia": 140
}
};
```
The library throws on invalid input rather than returning silently wrong results:
For a weighted graph:
- Include an edge in both directions if travel is allowed both ways
- Use different weights for each direction if costs differ (like uphill vs. downhill)
- Omit connections that aren't possible
| 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
The Dijkstra class provides three main methods for pathfinding:
### findShortestPath

@@ -153,3 +93,3 @@

**Throws:** Error only if the source node doesn't exist in the graph
**Throws:** See [Errors](#errors)

@@ -164,3 +104,3 @@ ---

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

@@ -172,3 +112,3 @@ | Parameter | Type | Description |

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

@@ -175,0 +115,0 @@ ---

-61
dist/commonjs/djisktra.d.ts
interface GraphNode {
[neighbor: string]: number;
}
interface Graph {
[node: string]: GraphNode;
}
/**
* Represents the result of a successful path finding operation
*/
interface ReachableResult {
status: 'reachable';
path: string[];
distance: number;
}
/**
* Represents the result when no path exists to the destination
*/
interface UnreachableResult {
status: 'unreachable';
}
/**
* Discriminated union type for path finding results
*/
type PathResult = ReachableResult | UnreachableResult;
declare class Djikstra {
/**
* Finds the shortest path between source and destination nodes.
* @param graph The graph represented as an adjacency list.
* @param source The source node ID.
* @param destination The destination node ID.
* @returns A PathResult object that indicates whether the destination is reachable.
* If reachable, includes the path and total distance.
* @throws Only if the source node doesn't exist in the graph.
*/
findShortestPath(graph: Graph, source: string, destination: string): PathResult;
/**
* Reconstructs the path from source to destination using the predecessor map.
* @param predecessors Map of nodes to their predecessors.
* @param destination The destination node.
* @returns Array of nodes from source to destination.
*/
private reconstructPath;
/**
* Computes shortest paths from a source to all reachable nodes.
* @param graph The graph represented as an adjacency list.
* @param source The source node ID.
* @returns Map of nodes to their distances from the source.
*/
computeAllPaths(graph: Graph, source: string): Record<string, number>;
/**
* Computes both distances and paths from a source to all reachable nodes.
* @param graph The graph represented as an adjacency list.
* @param source The source node ID.
* @returns Object containing distances and predecessors.
*/
computeDistancesAndPaths(graph: Graph, source: string): {
distances: Record<string, number>;
predecessors: Record<string, string>;
};
}
export default Djikstra;
-140
dist/commonjs/djisktra.js
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
const minHeap_js_1 = require("./minHeap.js");
class Djikstra {
/**
* Finds the shortest path between source and destination nodes.
* @param graph The graph represented as an adjacency list.
* @param source The source node ID.
* @param destination The destination node ID.
* @returns A PathResult object that indicates whether the destination is reachable.
* If reachable, includes the path and total distance.
* @throws Only if the source node doesn't exist in the graph.
*/
findShortestPath(graph, source, destination) {
// Validate inputs
if (!graph[source]) {
throw new Error(`Source node "${source}" does not exist in the graph.`);
}
const distances = {};
const predecessors = {};
const visited = new Set();
// Initialize distances
for (const node in graph) {
distances[node] = node === source ? 0 : Infinity;
}
// Priority queue for nodes to visit
const queue = new minHeap_js_1.MinHeap((a, b) => a.distance - b.distance);
queue.push({ node: source, distance: 0 });
while (!queue.isEmpty()) {
const current = queue.pop();
if (!current)
break;
const { node: currentNode, distance: currentDistance } = current;
// Skip if we've processed this node already or found a shorter path
if (visited.has(currentNode) || currentDistance > distances[currentNode]) {
continue;
}
// Mark as visited
visited.add(currentNode);
// If we reached the destination, we can stop
if (currentNode === destination) {
break;
}
// Check all neighbors
const neighbors = graph[currentNode] || {};
for (const neighbor in neighbors) {
if (visited.has(neighbor))
continue;
const edgeWeight = neighbors[neighbor];
const totalDistance = currentDistance + edgeWeight;
// If we found a shorter path to this neighbor
if (totalDistance < distances[neighbor]) {
distances[neighbor] = totalDistance;
predecessors[neighbor] = currentNode;
queue.push({ node: neighbor, distance: totalDistance });
}
}
}
// Check if destination is reachable
if (distances[destination] === Infinity) {
return { status: 'unreachable' };
}
// Reconstruct the path
const path = this.reconstructPath(predecessors, destination);
return {
status: 'reachable',
path,
distance: distances[destination],
};
}
/**
* Reconstructs the path from source to destination using the predecessor map.
* @param predecessors Map of nodes to their predecessors.
* @param destination The destination node.
* @returns Array of nodes from source to destination.
*/
reconstructPath(predecessors, destination) {
const path = [destination];
let current = destination;
while (predecessors[current]) {
current = predecessors[current];
path.unshift(current);
}
return path;
}
/**
* Computes shortest paths from a source to all reachable nodes.
* @param graph The graph represented as an adjacency list.
* @param source The source node ID.
* @returns Map of nodes to their distances from the source.
*/
computeAllPaths(graph, source) {
const result = this.computeDistancesAndPaths(graph, source);
return result.distances;
}
/**
* Computes both distances and paths from a source to all reachable nodes.
* @param graph The graph represented as an adjacency list.
* @param source The source node ID.
* @returns Object containing distances and predecessors.
*/
computeDistancesAndPaths(graph, source) {
if (!graph[source]) {
throw new Error(`Source node "${source}" does not exist in the graph.`);
}
const distances = {};
const predecessors = {};
const visited = new Set();
// Initialize distances
for (const node in graph) {
distances[node] = node === source ? 0 : Infinity;
}
const queue = new minHeap_js_1.MinHeap((a, b) => a.distance - b.distance);
queue.push({ node: source, distance: 0 });
while (!queue.isEmpty()) {
const current = queue.pop();
if (!current)
break;
const { node: currentNode, distance: currentDistance } = current;
if (visited.has(currentNode) || currentDistance > distances[currentNode]) {
continue;
}
visited.add(currentNode);
const neighbors = graph[currentNode] || {};
for (const neighbor in neighbors) {
if (visited.has(neighbor))
continue;
const edgeWeight = neighbors[neighbor];
const totalDistance = currentDistance + edgeWeight;
if (totalDistance < distances[neighbor]) {
distances[neighbor] = totalDistance;
predecessors[neighbor] = currentNode;
queue.push({ node: neighbor, distance: totalDistance });
}
}
}
return { distances, predecessors };
}
}
exports.default = Djikstra;
-2
dist/commonjs/index.d.ts
import Djikstra from './djisktra.js';
export default Djikstra;
-7
dist/commonjs/index.js
"use strict";
var __importDefault = (this && this.__importDefault) || function (mod) {
return (mod && mod.__esModule) ? mod : { "default": mod };
};
Object.defineProperty(exports, "__esModule", { value: true });
const djisktra_js_1 = __importDefault(require("./djisktra.js"));
exports.default = djisktra_js_1.default;
-47
dist/commonjs/minHeap.d.ts
/**
* A binary min-heap-based priority queue.
*/
export declare class MinHeap<T> {
private data;
private compare;
/**
* Creates a new MinHeap.
* @param compareFn A comparison function to determine priority.
*/
constructor(compareFn: (a: T, b: T) => number);
/**
* Inserts an item into the heap.
* @param item The item to insert.
*/
push(item: T): void;
/**
* Removes and returns the item with the highest priority (lowest cost).
* @returns The item with the highest priority, or undefined if the heap is empty.
*/
pop(): T | undefined;
/**
* Returns the highest priority item without removing it.
* @returns The highest priority item, or undefined if the heap is empty.
*/
peek(): T | undefined;
/**
* Returns the current size of the heap.
* @returns Number of elements in the heap.
*/
size(): number;
/**
* Checks if the heap is empty.
* @returns True if the heap is empty, false otherwise.
*/
isEmpty(): boolean;
/**
* Restores heap order by bubbling up the item at the given index.
* @param index The index of the item to bubble up.
*/
private bubbleUp;
/**
* Restores heap order by bubbling down the item at the given index.
* @param index The index of the item to bubble down.
*/
private bubbleDown;
}
-102
dist/commonjs/minHeap.js
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
exports.MinHeap = void 0;
/**
* A binary min-heap-based priority queue.
*/
class MinHeap {
/**
* Creates a new MinHeap.
* @param compareFn A comparison function to determine priority.
*/
constructor(compareFn) {
this.data = [];
this.compare = compareFn;
}
/**
* Inserts an item into the heap.
* @param item The item to insert.
*/
push(item) {
this.data.push(item);
this.bubbleUp(this.data.length - 1);
}
/**
* Removes and returns the item with the highest priority (lowest cost).
* @returns The item with the highest priority, or undefined if the heap is empty.
*/
pop() {
if (this.data.length === 0)
return undefined;
const top = this.data[0];
const bottom = this.data.pop();
if (this.data.length > 0 && bottom !== undefined) {
this.data[0] = bottom;
this.bubbleDown(0);
}
return top;
}
/**
* Returns the highest priority item without removing it.
* @returns The highest priority item, or undefined if the heap is empty.
*/
peek() {
return this.data[0];
}
/**
* Returns the current size of the heap.
* @returns Number of elements in the heap.
*/
size() {
return this.data.length;
}
/**
* Checks if the heap is empty.
* @returns True if the heap is empty, false otherwise.
*/
isEmpty() {
return this.data.length === 0;
}
/**
* Restores heap order by bubbling up the item at the given index.
* @param index The index of the item to bubble up.
*/
bubbleUp(index) {
const item = this.data[index];
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.compare(item, this.data[parentIndex]) >= 0)
break;
this.data[index] = this.data[parentIndex];
index = parentIndex;
}
this.data[index] = item;
}
/**
* Restores heap order by bubbling down the item at the given index.
* @param index The index of the item to bubble down.
*/
bubbleDown(index) {
const length = this.data.length;
const item = this.data[index];
while (true) {
const leftChildIndex = 2 * index + 1;
const rightChildIndex = 2 * index + 2;
let smallestIndex = index;
if (leftChildIndex < length &&
this.compare(this.data[leftChildIndex], this.data[smallestIndex]) < 0) {
smallestIndex = leftChildIndex;
}
if (rightChildIndex < length &&
this.compare(this.data[rightChildIndex], this.data[smallestIndex]) < 0) {
smallestIndex = rightChildIndex;
}
if (smallestIndex === index)
break;
this.data[index] = this.data[smallestIndex];
index = smallestIndex;
}
this.data[index] = item;
}
}
exports.MinHeap = MinHeap;
-3
dist/commonjs/package.json
{
"type": "commonjs"
}
-61
dist/esm/djisktra.d.ts
interface GraphNode {
[neighbor: string]: number;
}
interface Graph {
[node: string]: GraphNode;
}
/**
* Represents the result of a successful path finding operation
*/
interface ReachableResult {
status: 'reachable';
path: string[];
distance: number;
}
/**
* Represents the result when no path exists to the destination
*/
interface UnreachableResult {
status: 'unreachable';
}
/**
* Discriminated union type for path finding results
*/
type PathResult = ReachableResult | UnreachableResult;
declare class Djikstra {
/**
* Finds the shortest path between source and destination nodes.
* @param graph The graph represented as an adjacency list.
* @param source The source node ID.
* @param destination The destination node ID.
* @returns A PathResult object that indicates whether the destination is reachable.
* If reachable, includes the path and total distance.
* @throws Only if the source node doesn't exist in the graph.
*/
findShortestPath(graph: Graph, source: string, destination: string): PathResult;
/**
* Reconstructs the path from source to destination using the predecessor map.
* @param predecessors Map of nodes to their predecessors.
* @param destination The destination node.
* @returns Array of nodes from source to destination.
*/
private reconstructPath;
/**
* Computes shortest paths from a source to all reachable nodes.
* @param graph The graph represented as an adjacency list.
* @param source The source node ID.
* @returns Map of nodes to their distances from the source.
*/
computeAllPaths(graph: Graph, source: string): Record<string, number>;
/**
* Computes both distances and paths from a source to all reachable nodes.
* @param graph The graph represented as an adjacency list.
* @param source The source node ID.
* @returns Object containing distances and predecessors.
*/
computeDistancesAndPaths(graph: Graph, source: string): {
distances: Record<string, number>;
predecessors: Record<string, string>;
};
}
export default Djikstra;
-138
dist/esm/djisktra.js
import { MinHeap } from './minHeap.js';
class Djikstra {
/**
* Finds the shortest path between source and destination nodes.
* @param graph The graph represented as an adjacency list.
* @param source The source node ID.
* @param destination The destination node ID.
* @returns A PathResult object that indicates whether the destination is reachable.
* If reachable, includes the path and total distance.
* @throws Only if the source node doesn't exist in the graph.
*/
findShortestPath(graph, source, destination) {
// Validate inputs
if (!graph[source]) {
throw new Error(`Source node "${source}" does not exist in the graph.`);
}
const distances = {};
const predecessors = {};
const visited = new Set();
// Initialize distances
for (const node in graph) {
distances[node] = node === source ? 0 : Infinity;
}
// Priority queue for nodes to visit
const queue = new MinHeap((a, b) => a.distance - b.distance);
queue.push({ node: source, distance: 0 });
while (!queue.isEmpty()) {
const current = queue.pop();
if (!current)
break;
const { node: currentNode, distance: currentDistance } = current;
// Skip if we've processed this node already or found a shorter path
if (visited.has(currentNode) || currentDistance > distances[currentNode]) {
continue;
}
// Mark as visited
visited.add(currentNode);
// If we reached the destination, we can stop
if (currentNode === destination) {
break;
}
// Check all neighbors
const neighbors = graph[currentNode] || {};
for (const neighbor in neighbors) {
if (visited.has(neighbor))
continue;
const edgeWeight = neighbors[neighbor];
const totalDistance = currentDistance + edgeWeight;
// If we found a shorter path to this neighbor
if (totalDistance < distances[neighbor]) {
distances[neighbor] = totalDistance;
predecessors[neighbor] = currentNode;
queue.push({ node: neighbor, distance: totalDistance });
}
}
}
// Check if destination is reachable
if (distances[destination] === Infinity) {
return { status: 'unreachable' };
}
// Reconstruct the path
const path = this.reconstructPath(predecessors, destination);
return {
status: 'reachable',
path,
distance: distances[destination],
};
}
/**
* Reconstructs the path from source to destination using the predecessor map.
* @param predecessors Map of nodes to their predecessors.
* @param destination The destination node.
* @returns Array of nodes from source to destination.
*/
reconstructPath(predecessors, destination) {
const path = [destination];
let current = destination;
while (predecessors[current]) {
current = predecessors[current];
path.unshift(current);
}
return path;
}
/**
* Computes shortest paths from a source to all reachable nodes.
* @param graph The graph represented as an adjacency list.
* @param source The source node ID.
* @returns Map of nodes to their distances from the source.
*/
computeAllPaths(graph, source) {
const result = this.computeDistancesAndPaths(graph, source);
return result.distances;
}
/**
* Computes both distances and paths from a source to all reachable nodes.
* @param graph The graph represented as an adjacency list.
* @param source The source node ID.
* @returns Object containing distances and predecessors.
*/
computeDistancesAndPaths(graph, source) {
if (!graph[source]) {
throw new Error(`Source node "${source}" does not exist in the graph.`);
}
const distances = {};
const predecessors = {};
const visited = new Set();
// Initialize distances
for (const node in graph) {
distances[node] = node === source ? 0 : Infinity;
}
const queue = new MinHeap((a, b) => a.distance - b.distance);
queue.push({ node: source, distance: 0 });
while (!queue.isEmpty()) {
const current = queue.pop();
if (!current)
break;
const { node: currentNode, distance: currentDistance } = current;
if (visited.has(currentNode) || currentDistance > distances[currentNode]) {
continue;
}
visited.add(currentNode);
const neighbors = graph[currentNode] || {};
for (const neighbor in neighbors) {
if (visited.has(neighbor))
continue;
const edgeWeight = neighbors[neighbor];
const totalDistance = currentDistance + edgeWeight;
if (totalDistance < distances[neighbor]) {
distances[neighbor] = totalDistance;
predecessors[neighbor] = currentNode;
queue.push({ node: neighbor, distance: totalDistance });
}
}
}
return { distances, predecessors };
}
}
export default Djikstra;
-2
dist/esm/index.d.ts
import Djikstra from './djisktra.js';
export default Djikstra;
-2
dist/esm/index.js
import Djikstra from './djisktra.js';
export default Djikstra;
-47
dist/esm/minHeap.d.ts
/**
* A binary min-heap-based priority queue.
*/
export declare class MinHeap<T> {
private data;
private compare;
/**
* Creates a new MinHeap.
* @param compareFn A comparison function to determine priority.
*/
constructor(compareFn: (a: T, b: T) => number);
/**
* Inserts an item into the heap.
* @param item The item to insert.
*/
push(item: T): void;
/**
* Removes and returns the item with the highest priority (lowest cost).
* @returns The item with the highest priority, or undefined if the heap is empty.
*/
pop(): T | undefined;
/**
* Returns the highest priority item without removing it.
* @returns The highest priority item, or undefined if the heap is empty.
*/
peek(): T | undefined;
/**
* Returns the current size of the heap.
* @returns Number of elements in the heap.
*/
size(): number;
/**
* Checks if the heap is empty.
* @returns True if the heap is empty, false otherwise.
*/
isEmpty(): boolean;
/**
* Restores heap order by bubbling up the item at the given index.
* @param index The index of the item to bubble up.
*/
private bubbleUp;
/**
* Restores heap order by bubbling down the item at the given index.
* @param index The index of the item to bubble down.
*/
private bubbleDown;
}
-98
dist/esm/minHeap.js
/**
* A binary min-heap-based priority queue.
*/
export class MinHeap {
/**
* Creates a new MinHeap.
* @param compareFn A comparison function to determine priority.
*/
constructor(compareFn) {
this.data = [];
this.compare = compareFn;
}
/**
* Inserts an item into the heap.
* @param item The item to insert.
*/
push(item) {
this.data.push(item);
this.bubbleUp(this.data.length - 1);
}
/**
* Removes and returns the item with the highest priority (lowest cost).
* @returns The item with the highest priority, or undefined if the heap is empty.
*/
pop() {
if (this.data.length === 0)
return undefined;
const top = this.data[0];
const bottom = this.data.pop();
if (this.data.length > 0 && bottom !== undefined) {
this.data[0] = bottom;
this.bubbleDown(0);
}
return top;
}
/**
* Returns the highest priority item without removing it.
* @returns The highest priority item, or undefined if the heap is empty.
*/
peek() {
return this.data[0];
}
/**
* Returns the current size of the heap.
* @returns Number of elements in the heap.
*/
size() {
return this.data.length;
}
/**
* Checks if the heap is empty.
* @returns True if the heap is empty, false otherwise.
*/
isEmpty() {
return this.data.length === 0;
}
/**
* Restores heap order by bubbling up the item at the given index.
* @param index The index of the item to bubble up.
*/
bubbleUp(index) {
const item = this.data[index];
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.compare(item, this.data[parentIndex]) >= 0)
break;
this.data[index] = this.data[parentIndex];
index = parentIndex;
}
this.data[index] = item;
}
/**
* Restores heap order by bubbling down the item at the given index.
* @param index The index of the item to bubble down.
*/
bubbleDown(index) {
const length = this.data.length;
const item = this.data[index];
while (true) {
const leftChildIndex = 2 * index + 1;
const rightChildIndex = 2 * index + 2;
let smallestIndex = index;
if (leftChildIndex < length &&
this.compare(this.data[leftChildIndex], this.data[smallestIndex]) < 0) {
smallestIndex = leftChildIndex;
}
if (rightChildIndex < length &&
this.compare(this.data[rightChildIndex], this.data[smallestIndex]) < 0) {
smallestIndex = rightChildIndex;
}
if (smallestIndex === index)
break;
this.data[index] = this.data[smallestIndex];
index = smallestIndex;
}
this.data[index] = item;
}
}
-3
dist/esm/package.json
{
"type": "module"
}