dijkstra

@algorithm.ts/dijkstra

A typescript implementation of the dijkstra algorithm.

The following definition is quoted from Wikipedia (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm):

Dijkstra's algorithm (/ˈdaɪkstrəz/ DYKE-strəz) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

Install

• npm

  npm install --save @algorithm.ts/dijkstra

• yarn

  yarn add @algorithm.ts/dijkstra

Usage

• Simple

  import dijkstra from '@algorithm.ts/dijkstra'
  
  const { dist } = dijkstra({
    N: 4,
    source: 0,
    edges: [
      { to: 1, cost: 2 },
      { to: 2, cost: 2 },
      { to: 3, cost: 2 },
      { to: 3, cost: 1 },
    ],
    G: [[0], [1, 2], [3], []],
  })
  // => [0, 2, 4, 4]
  //
  //    Which means:
  //      0 --> 0: cost is 0
  //      0 --> 1: cost is 2
  //      0 --> 2: cost is 4
  //      0 --> 3: cost is 4

Example

• A solution for leetcode "Number of Ways to Arrive at Destination" (https://leetcode.com/problems/number-of-ways-to-arrive-at-destination/):

  import type { IDijkstraEdge } from '@algorithm.ts/dijkstra'
  import { dijkstra } from '@algorithm.ts/dijkstra'
  
  const MOD = 1e9 + 7
  export function countPaths(N: number, roads: number[][]): number {
    const edges: Array<IDijkstraEdge<number>> = []
    const G: number[][] = new Array(N)
    for (let i = 0; i < N; ++i) G[i] = []
    for (const [from, to, cost] of roads) {
      G[from].push(edges.length)
      edges.push({ to, cost })
  
      G[to].push(edges.length)
      edges.push({ to: from, cost })
    }
  
    const source = 0
    const target = N - 1
    const { dist } = dijkstra({ N, source: target, edges, G }, { INF: 1e12 })
  
    const dp: number[] = new Array(N).fill(-1)
    return dfs(source)
  
    function dfs(o: number): number {
      if (o === target) return 1
  
      let answer = dp[o]
      if (answer !== -1) return answer
  
      answer = 0
      const d = dist[o]
      for (const idx of G[o]) {
        const e: IDijkstraEdge<number> = edges[idx]
        if (dist[e.to] + e.cost === d) {
          const t = dfs(e.to)
          answer = modAdd(answer, t)
        }
      }
      dp[o] = answer
      return answer
    }
  }
  
  function modAdd(x: number, y: number): number {
    const z: number = x + y
    return z < MOD ? z : z - MOD
  }

Related

• 《算法竞赛入门经典（第 2 版）》（刘汝佳）： P359-P362 Dijkstra 算法
• dijkstra 算法 | 光和尘
• dijkstra | Wikipedia
• @algorithm.ts/queue