Dijkstra's Algorithm Implementation

1.0.3 · maintenance · verified Sun Apr 19

dijkstrajs is a lightweight, zero-dependency JavaScript library that provides a straightforward implementation of Dijkstra's single-source shortest-paths algorithm. Currently at version 1.0.3, the package was last published over three years ago, indicating a mature and stable codebase rather than active feature development. It is designed for use in Node.js environments and offers a simple API for finding the shortest path between two nodes in a weighted graph. While other Dijkstra implementations might offer performance optimizations like priority queues, dijkstrajs prioritizes simplicity and ease of integration for basic graph traversal needs. Developers should note its inherent limitation of not supporting negative edge weights, which is a fundamental constraint of Dijkstra's algorithm itself.

Common errors

```
TypeError: (0 , dijkstrajs__WEBPACK_IMPORTED_MODULE_0__.findPath) is not a function
```
cause Attempting to import `findPath` using a default import or a CommonJS `require` call that doesn't destructure the `findPath` property from the module object in an ESM context.

fix Use a named import for ESM: `import { findPath } from 'dijkstrajs'`. For CommonJS, ensure proper destructuring: `const { findPath } = require('dijkstrajs')`.
```
TypeError: Cannot read properties of undefined (reading 'findPath')
```
cause This typically occurs in CommonJS environments when `require('dijkstrajs')` is assigned to a variable, and then `.findPath` is called on it, but the default export isn't the expected object, or the import path is incorrect.

fix Verify the `require` statement accurately destructures `findPath`: `const { findPath } = require('dijkstrajs')`. Ensure the package is correctly installed.
```
Path not found (or similar message/null return for unreachable nodes)
```
cause The `findPath` function returns `null` or an empty path when the target node is unreachable from the source node within the given graph, or if the graph is disconnected.

fix Validate that the source and target nodes exist in the graph and that there is a connected path between them. Handle the `null` return explicitly in your application logic.

Warnings

gotcha Dijkstra's algorithm, and consequently this library, does not correctly compute shortest paths if the graph contains edges with negative weights. For graphs with negative weights, consider algorithms like Bellman-Ford or SPFA.
Fix: Ensure all edge weights in your graph are non-negative, or use an alternative algorithm for graphs with negative weights.
gotcha The library is a 'simple implementation' and does not explicitly state the use of an optimized data structure like a min-priority queue. For very large or dense graphs, performance might be slower than implementations that utilize such optimizations (e.g., O(E log V) vs. O(V^2)).
Fix: For performance-critical applications with large graphs, benchmark this library against alternatives that explicitly mention priority queue optimizations.
gotcha The expected graph input format is an adjacency list represented as a JavaScript object, where keys are node names and values are objects mapping neighbor nodes to their respective edge weights. Deviating from this format will lead to incorrect results or errors.
Fix: Refer to the quickstart example for the precise graph object structure required by `dijkstrajs`.
deprecated The package has not been updated in over three years (last published 3+ years ago). While stable, this indicates a lack of active development, bug fixes, or new features. Users should be aware that new Node.js versions or JavaScript features might not be officially supported or tested.
Fix: Consider testing thoroughly with newer Node.js runtimes. For projects requiring active maintenance or advanced features, explore more recently updated graph libraries.

Install

npm install dijkstrajs npm
yarn add dijkstrajs yarn
pnpm add dijkstrajs pnpm

Imports

findPath
wrong:
```
import dijkstra from 'dijkstrajs'
```
correct:
```
import { findPath } from 'dijkstrajs'
```
The library exports an object with a 'findPath' method, not a default function. This applies to both ESM and CJS.
findPath (CommonJS)
wrong:
```
const dijkstra = require('dijkstrajs')
```
correct:
```
const { findPath } = require('dijkstrajs')
```
For CommonJS, destructure the 'findPath' method from the required module object.

Quickstart

This example demonstrates how to define a weighted graph using an adjacency list and then use `findPath` to calculate the shortest path between specified start and end nodes.

import { findPath } from 'dijkstrajs';

const graph = {
  A: { B: 1, C: 4 },
  B: { A: 1, C: 2, D: 5 },
  C: { A: 4, B: 2, D: 1 },
  D: { B: 5, C: 1 },
  E: { F: 3 }, // Disconnected node
  F: { E: 3 }
};

// Find the shortest path from node A to node D
const pathAD = findPath(graph, 'A', 'D');
console.log('Path from A to D:', pathAD); // Expected: [ 'A', 'B', 'C', 'D' ]

// Find the shortest path from node A to node E (unreachable)
const pathAE = findPath(graph, 'A', 'E');
console.log('Path from A to E:', pathAE); // Expected: null (or similar indication of no path)

// Example with different start/end
const pathBD = findPath(graph, 'B', 'D');
console.log('Path from B to D:', pathBD); // Expected: [ 'B', 'C', 'D' ]

view raw JSON →