Dijkstra's algorithm

This repos contains an implementation of dijkstra's algorithm that can be used with any data structure.

Dijkstra's algorithm is a variant of the BFS algorithm that finds the shortest path between two nodes in a graph.

Motivation

I discovered the Dijkstra's algorithm when I was working on advent-of-code 2021 day 15. Each example of the algorithm implementation was very specific to the data structure of the current use case, so I tried to write a generic and flexible implementation with the help of Paul Brauner.

Dijkstra's function can accept different data structure as input: (example of inputs used in unit tests)

1. On this 2D matrix (from advent-of-code example), each vertex is a vec2 coordinate (y, x) when the cost of the path is number of the cooridnate.

const matrix = [
  [1, 1, 6, 3, 7, 5, 1, 7, 4, 2],
  [1, 3, 8, 1, 3, 7, 3, 6, 7, 2],
  [2, 1, 3, 6, 5, 1, 1, 3, 2, 8],
  [3, 6, 9, 4, 9, 3, 1, 5, 6, 9],
  [7, 4, 6, 3, 4, 1, 7, 1, 1, 1],
  [1, 3, 1, 9, 1, 2, 8, 1, 3, 7],
  [1, 3, 5, 9, 9, 1, 2, 4, 2, 1],
  [3, 1, 2, 5, 4, 2, 1, 6, 3, 9],
  [1, 2, 9, 3, 1, 3, 8, 5, 2, 1],
  [2, 3, 1, 1, 9, 4, 4, 5, 8, 1],
]

2. This graph can be used too when object keys are verticies and values are neighbors associated to there own cost.

const graph = {
  start: { A: 5, B: 2 },
  A: { start: 1, C: 4, D: 2 },
  B: { A: 8, D: 7 },
  C: { D: 6, finish: 3 },
  D: { finish: 1 },
  finish: {},
}

Usage

In order to accept different data structures, dijkstra recieves some functions as params:

• getNeighbors: (v: GVertex) => GVertex[] returns array of vertices that are neighbors of v
• getCostBetweenVertices: (a: GVertex, b: GVertex) => number returns cost of edge between thwo vertices
• source: GVertex vertex from which algorithm starts
• isTarget: (vertex: GVertex) => boolean returns true if vertex is the target
• queue = priorityQueueMinHeap<GVertex>() queue that is used to store vertices in order of their distance from source

exemple of usage:

const getNeighbors = (vertex) => Object.keys(graph[vertex])
const distanceBetweenTwoVertices = (v1, v2) => graph[v1][v2]
const isTarget = (vertex) => vertex === "finish"

const shortestPathCost: number = dijkstra<string>(
  getNeighbors,
  distanceBetweenTwoVertices,
  "start",
  isTarget
)

dijkstra returns the shortest path cost from source to target

Priority Queue

This algorithm is using a priority queue to store vertices in order of their distance from source. The last one is a big part of Dijkstra implementation if we want to use it with big data structures.

Two types of priority queue have been tested in this algorithm:

• priority Queue min (O(n)complexity)
• priority Queue min with binary heap (O(log n)complexity)

The second one will be more efficient because binary heap doesn't require us to iterate over the list.

Requirement

• node js >= 16
• npm >= 8

test it

• Clone the repos

$ git clone [email protected]:willybrauner/dijkstra-algorithm.git

• Install dépendencies

$ npm i

• Start tests once

$ npm run test

• Start tests in watch mode

$ npm run test:watch

Credits

© Willy Brauner & Paul Brauner