Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 | 16x 16x 22x 29x 16x 22x 22x 22x 58x 58x 58x 58x 58x 2x 56x 37x 37x 37x 22x 71x 71x 71x 22x 62x 62x 62x 7x 55x 20x 20x 63x 63x 20x | import Graph, { DefaultEdgeType } from '../Graph';
import PriorityQueue from './PriorityQueue';
const DEFAULT_WEIGHT_FUNC = () => 1;
/**
* @description Dijkstra's algorithm for single-source shortest paths.
* @description https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
* @description.zh-CN Dijkstra 算法用于单源最短路径。
*/
const dijkstra = <NodeIDType, EdgeType>(
graph: Graph<NodeIDType, any, EdgeType>,
source: NodeIDType,
weightFn?: (node: DefaultEdgeType<NodeIDType, EdgeType>) => number,
edgeFn?: (node: NodeIDType) => DefaultEdgeType<NodeIDType, EdgeType>[],
) => {
return runDijkstra<NodeIDType, EdgeType>(
graph,
source,
weightFn || DEFAULT_WEIGHT_FUNC,
edgeFn ||
function (v: NodeIDType) {
return graph.outEdges(v)!;
},
);
};
type Entry<NodeIDType> = {
distance: number;
predecessor?: NodeIDType;
};
/**
* @description Dijkstra's algorithm for single-source shortest paths.
* @description https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
* @description.zh-CN Dijkstra 算法用于单源最短路径。
*/
const runDijkstra = <NodeIDType, EdgeType>(
graph: Graph<NodeIDType, any, EdgeType>,
source: NodeIDType,
weightFn: (node: DefaultEdgeType<NodeIDType, EdgeType>) => number,
edgeFn: (node: NodeIDType) => DefaultEdgeType<NodeIDType, EdgeType>[],
) => {
const results: Map<NodeIDType, Entry<NodeIDType>> = new Map();
const pq = new PriorityQueue<NodeIDType>();
let v: NodeIDType | undefined;
let vEntry: Entry<NodeIDType> | undefined;
const updateNeighbors = (edge: DefaultEdgeType<NodeIDType, EdgeType>) => {
const w = edge.v !== v ? edge.v : edge.w;
const wEntry = results.get(w)!;
const weight = weightFn(edge);
const distance = vEntry!.distance + weight;
if (weight < 0) {
throw new Error(
'dijkstra does not allow negative edge weights. ' +
'Bad edge: ' +
edge +
' Weight: ' +
weight,
);
}
// If there is already a shorter path to w, ignore this edge.
if (distance < wEntry.distance) {
wEntry.distance = distance;
wEntry.predecessor = v;
pq.decrease(w, distance);
}
};
graph.nodes().forEach((v) => {
const distance = v === source ? 0 : Number.POSITIVE_INFINITY;
results.set(v, { distance });
pq.add(v, distance);
});
while (pq.size() > 0) {
v = pq.removeMin()!;
vEntry = results.get(v);
if (vEntry && vEntry.distance === Number.POSITIVE_INFINITY) {
break;
}
edgeFn(v).forEach(updateNeighbors);
}
const obj = {} as Record<string, Entry<NodeIDType>>;
Array.from(results.entries()).forEach(([node, e]) => {
obj[String(node)] = e;
return obj;
});
return obj;
};
export default dijkstra;
|