# graphology-shortest-path

> Shortest path functions for graphology.

Latest version **2.1.0** (published 2024-03-27) · MIT license · 0 weekly downloads

## Install

```sh
npm install graphology-shortest-path
pnpm add graphology-shortest-path
yarn add graphology-shortest-path
bun add graphology-shortest-path
```

## Health

**Score 40/100 (D)** — status: abandoned.

Positive: has types; no vulnerabilities; high maintenance score; high quality score.

Warnings: low downloads; no esm support.

Negative: abandoned.

## Facts

| | |
|---|---|
| Version | 2.1.0 |
| Published | 2024-03-27 |
| First published | 2017-02-17 |
| Weekly downloads | 0 |
| License | MIT |
| TypeScript types | bundled |
| Module format | CommonJS |
| Dependencies | 4 |
| Unpacked size | 39.6 KB |
| Known vulnerabilities | 0 |
| Install scripts | no |
| GitHub stars | 1744 |
| Author | Guillaume Plique |
| Maintainers | yomguithereal |
| Keywords | graph, graphology, shortest path, dijkstra, a star |

## Links

- npm: https://www.npmjs.com/package/graphology-shortest-path
- Repository: https://github.com/graphology/graphology
- Homepage: https://github.com/graphology/graphology#readme
- Issues: https://github.com/graphology/graphology/issues
- npm.io page: https://npm.io/package/graphology-shortest-path

## Dependencies (4)

- [mnemonist](https://npm.io/package/mnemonist.md) ^0.39.0
- [graphology-utils](https://npm.io/package/graphology-utils.md) ^2.4.3
- [graphology-indices](https://npm.io/package/graphology-indices.md) ^0.17.0
- [@yomguithereal/helpers](https://npm.io/package/@yomguithereal/helpers.md) ^1.1.1

## Alternatives

- [base64url](https://npm.io/package/base64url.md) — 6.1M weekly downloads
- [get-installed-path](https://npm.io/package/get-installed-path.md) — 502.9K weekly downloads
- [@uppy/url](https://npm.io/package/@uppy/url.md) — 185.8K weekly downloads
- [@d3fc/d3fc-shape](https://npm.io/package/@d3fc/d3fc-shape.md) — 16.2K weekly downloads
- [localizer](https://npm.io/package/localizer.md) — 226 weekly downloads

## Recent versions

- 2.1.0 (latest) — 2024-03-27
- 1.1.0-alpha1 (alpha) — 2020-02-27
- 2.0.2 — 2023-03-03
- 2.0.1 — 2022-04-21
- 2.0.0 — 2021-12-09
- 1.5.2 — 2021-11-12
- 1.5.1 — 2021-11-08
- 1.5.0 — 2021-10-31
- 1.4.2 — 2021-10-15
- 1.4.1 — 2020-12-22
- 1.4.0 — 2020-11-09
- 1.3.4 — 2020-07-27
- 1.3.3 — 2020-06-15
- 1.3.2 — 2020-06-12
- 1.3.1 — 2020-03-30
- … 10 more at https://npm.io/package/graphology-shortest-path/versions

## README

# Graphology Shortest Path

Shortest path functions for [`graphology`](https://graphology.github.io).

## Installation

```
npm install graphology-shortest-path
```

## Usage

- [Unweighted](#unweighted)
  - [bidirectional](#bidirectional)
  - [singleSource](#singlesource)
  - [singleSourceLength](#singlesourcelength)
  - [undirectedSingleSourceLength](#undirectedsinglesourcelength)
- [Dijkstra](#dijkstra)
  - [bidirectional](#dijkstra-bidirectional)
  - [singleSource](#dijkstra-singlesource)
- [A-star](#a-star)
  - [bidirectional](#astar-bidirectional)
- [Utilities](#utilities)
  - [edgePathFromNodePath](#edgepathfromnodepath)

## Unweighted

### bidirectional

Returns the shortest path in the graph between source & target or `null` if such a path does not exist.

```js
import {bidirectional} from 'graphology-shortest-path';
// Alternatively, if you want to load only the relevant code
import {bidirectional} from 'graphology-shortest-path/unweighted';

// Returning the shortest path between source & target
const path = bidirectional(graph, source, target);
```

_Arguments_

- **graph** _Graph_: a `graphology` instance.
- **source** _any_: source node.
- **target** _any_: target node.

### singleSource

Return a map of every shortest path between the given source & all the nodes of the graph.

```js
import {singleSource} from 'graphology-shortest-path';
// Alternatively, if you want to load only the relevant code
import {singleSource} from 'graphology-shortest-path/unweighted';

// Returning every shortest path between source & every node of the graph
const paths = singleSource(graph, source);
```

_Arguments_

- **graph** _Graph_: a `graphology` instance.
- **source** _any_: source node.

### singleSourceLength

Return a map of every shortest path length between the given source & all the nodes of the graph.

```js
import {singleSourceLength} from 'graphology-shortest-path';
// Alternatively, if you want to load only the relevant code
import {singleSourceLength} from 'graphology-shortest-path/unweighted';

// Returning every shortest path between source & every node of the graph
const paths = singleSourceLength(graph, source);
```

_Arguments_

- **graph** _Graph_: a `graphology` instance.
- **source** _any_: source node.

### undirectedSingleSourceLength

Return a map of every shortest path length between the given source & all the nodes of the graph. This is basically the same as [singleSourceLength](#singlesourcelength) except that it will consider any given graph as undirected when traversing.

```js
import {undirectedSingleSourceLength} from 'graphology-shortest-path';
// Alternatively, if you want to load only the relevant code
import {undirectedSingleSourceLength} from 'graphology-shortest-path/unweighted';

// Returning every shortest path between source & every node of the graph
const paths = undirectedSingleSourceLength(graph, source);
```

_Arguments_

- **graph** _Graph_: a `graphology` instance.
- **source** _any_: source node.

## Dijkstra

<h3 id="dijkstra-bidirectional">bidirectional</h3>

Returns the shortest path in the weighted graph between source & target or `null` if such a path does not exist.

```js
import {dijkstra} from 'graphology-shortest-path';
// Alternatively, if you want to load only the relevant code
import dijkstra from 'graphology-shortest-path/dijkstra';

// Returning the shortest path between source & target
const path = dijkstra.bidirectional(graph, source, target);

// If you store edges' weight in custom attribute
const path = dijkstra.bidirectional(graph, source, target, 'customWeight');

// Using a custom weight getter function
const path = dijkstra.bidirectional(
  graph,
  source,
  target,
  (_, attr) => attr.importance
);
```

_Arguments_

- **graph** _Graph_: a `graphology` instance.
- **source** _any_: source node.
- **target** _any_: target node.
- **getEdgeWeight** _?string\|function_ [`weight`]: name of the weight attribute or getter function.

<h3 id="dijkstra-singlesource">singleSource</h3>

Return a map of every shortest path between the given source & all the nodes of the weighted graph.

```js
import {dijkstra} from 'graphology-shortest-path';
// Alternatively, if you want to load only the relevant code
import dijkstra from 'graphology-shortest-path/dijkstra';

// Returning every shortest path between source & every node of the graph
const paths = dijkstra.singleSource(graph, source);

// If you store edges' weight in custom attribute
const paths = dijkstra.singleSource(graph, source, 'customWeight');

// Using a custom weight getter function
const path = dijkstra.singleSource(graph, source, (_, attr) => attr.importance);
```

_Arguments_

- **graph** _Graph_: a `graphology` instance.
- **source** _any_: source node.
- **getEdgeWeight** _?string\|function_ [`weight`]: name of the weight attribute or getter function.

## A-star

<h3 id="astar-bidirectional">bidirectional</h3>

Returns the shortest path in the weighted graph between source & target or `null` if such a path does not exist.

```js
import {astar} from 'graphology-shortest-path';
// Alternatively, if you want to load only the relevant code
import astar from 'graphology-shortest-path/astar';

// Returning the shortest path between source & target
const path = astar.bidirectional(
  graph,
  source,
  target,
  (_, attr) => attr.importance
  (node, finalTarget) => euclideanDistance(points[node], points[finalTarget])
);
```

_Arguments_

- **graph** _Graph_: a `graphology` instance.
- **source** _any_: source node.
- **target** _any_: target node.
- **getEdgeWeight** _?string\|function_ [`weight`]: name of the weight attribute or getter function.
- **heuristic** _?function_: heuristic function to compute distance between current node and final target.

## Utilities

### edgePathFromNodePath

Helper function that can convert a node path to an edge path.

```js
import {edgePathFromNodePath} from 'graphology-shortest-path';
// Alternatively, if you want to load only the relevant code
import {edgePathFromNodePath} from 'graphology-shortest-path/utils';

const edgePath = edgePathFromNodePath(graph, nodePath);
```

_Arguments_

- **graph** _Graph_: a `graphology` instance.
- **nodePath** _Array_: node path to convert.

---
_Source: https://npm.io/package/graphology-shortest-path · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._