import { BinaryHeap } from './binary-heap' ; const buildPrecedentsMap = ( graph , startNode , endNode ) => { const precedentsMap = { } ; const visited = { } ; const storedShortestPaths = { } ; storedShortestPaths [ startNode ] = 0 ; const pQueue = new ( BinaryHeap as any ) ( ( n ) => n . weight ) ; pQueue . push ( { id : startNode , weight : 0 } ) ; while ( pQueue . size ( ) ) { const shortestNode = pQueue . pop ( ) ; const shortestNodeId = shortestNode . id ; if ( visited [ shortestNodeId ] ) continue ; const neighboringNodes = graph ( shortestNodeId ) || { } ; visited [ shortestNodeId ] = 1 ; for ( let neighbor in neighboringNodes ) { const newTotalWeight = shortestNode . weight + neighboringNodes [ neighbor ] ; if ( typeof storedShortestPaths [ neighbor ] === 'undefined' || storedShortestPaths [ neighbor ] > newTotalWeight ) { storedShortestPaths [ neighbor ] = newTotalWeight ; pQueue . push ( { id : neighbor , weight : newTotalWeight } ) ; precedentsMap [ neighbor ] = shortestNodeId ; } } } if ( typeof storedShortestPaths [ endNode ] === 'undefined' ) { throw new Error ( `There is no path from ${ startNode } to ${ endNode }` ) ; } return precedentsMap ; } ; const getPathFromPrecedentsMap = ( precedentsMap , endNode ) => { const nodes = [ ] ; let n = endNode ; while ( n ) { nodes . push ( n ) ; n = precedentsMap [ n ] ; } return nodes . reverse ( ) ; } ; export const findShortestPath = ( graph , startNode , endNode ) => { const precedentsMap = buildPrecedentsMap ( graph , startNode , endNode ) ; return getPathFromPrecedentsMap ( precedentsMap , endNode ) ; } ;