Docs
Dijkstra

Dijkstra

A hook for implementing dijkstra.

About

The useDijkstra hook is a custom React hook that provides an implementation of Dijkstra’s shortest path algorithm. It is designed to calculate the shortest path from a starting node to a target node in a graph. The hook supports graphs represented as adjacency lists, handles edge cases like disconnected nodes, and allows dynamic updates to the graph structure.

Parameters

NameTypeDescription
graphRecord<string, Record<string, number>>The adjacency list representation of the graph, where keys are node IDs and values are their neighbors and edge weights.
startstringThe starting node from which to calculate the shortest path.
targetstringThe target node to which the shortest path should be calculated.
onComplete`(path: string[], distance: number or null) => voidOptional. Callback function that gets called after calculation completes.

Return Values

NameTypeDescription
shortestPathstring[]The calculated shortest path as an array of node IDs.
distancenumber or null
isProcessingbooleanA boolean indicating if the algorithm is currently calculating the shortest path.
startDijkstra(graph: Record<string, Record<string, number>>, start: string, target: string, onComplete?: (path: string[], distance: number or null) => void) => void
reset() => voidA function to reset the hook's state, clearing the result and processing status.

Installation

Run the following command:

npx scriptkavi-hooks@latest add dijkstra

Usage

import { useDijkstra } from "@/hooks/dijkstra"

Finding the Shortest Path in a Graph

import React from "react"
 
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 },
}
 
function DijkstraComponent() {
  const { shortestPath, distance, isProcessing, startDijkstra, reset } =
    useDijkstra()
 
  return (
    <div>
      <h3>Graph: {JSON.stringify(graph)}</h3>
      <h3>
        Shortest Path:{" "}
        {shortestPath.length > 0 ? shortestPath.join(" -> ") : "No Path"}
      </h3>
      <h3>Distance: {distance !== null ? distance : "N/A"}</h3>
 
      <button
        onClick={() => startDijkstra(graph, "A", "D")}
        disabled={isProcessing}
      >
        {isProcessing ? "Calculating..." : "Find Shortest Path from A to D"}
      </button>
 
      <button onClick={reset} disabled={isProcessing}>
        Reset
      </button>
    </div>
  )
}
 
export default DijkstraComponent

Completion Callback

You can also pass a completion callback that will be triggered when the algorithm completes, allowing you to execute additional logic after the shortest path has been calculated.

import React from "react"
 
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 },
}
 
const DijkstraCallbackComponent = () => {
  const { startDijkstra, shortestPath, distance, isProcessing } = useDijkstra()
 
  return (
    <div>
      <h3>
        Shortest Path:{" "}
        {shortestPath.length > 0 ? shortestPath.join(" -> ") : "No Path"}
      </h3>
      <h3>Distance: {distance !== null ? distance : "N/A"}</h3>
 
      <button
        onClick={() =>
          startDijkstra(graph, "A", "D", (path, dist) => {
            console.log("Shortest path:", path, "Distance:", dist)
          })
        }
        disabled={isProcessing}
      >
        {isProcessing ? "Calculating..." : "Find Path with Callback"}
      </button>
    </div>
  )
}
 
export default DijkstraCallbackComponent

Considerations

  • Non-Negative Weights: Dijkstra’s algorithm assumes non-negative edge weights. If negative weights are present, consider using the Bellman-Ford algorithm instead.

  • Disconnected Graph: If there is no path between the start and target nodes, the hook will return null for both the shortest path and distance.

Depth First SearchGraham Scan