20198813057

Committed 13 Dec 2025 10:31PM UTC coverage: 86.318% (-4.8%) from 91.088%

Build # 20198813057

Build Type

push

github

Committed by

apowers313

Commit Message

fix: algorithm exports

Run Details

2508 of 2962 branches covered (84.67%)

Branch coverage included in aggregate %.

9056 of 10435 relevant lines covered (86.78%)

693539.89 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

88.8

/src/algorithms/shortest-path/dijkstra.ts

import type {Graph} from "../../core/graph.js";
import {PriorityQueue} from "../../data-structures/priority-queue.js";
import type {DijkstraOptions, NodeId, ShortestPathResult} from "../../types/index.js";
import {reconstructPath} from "../../utils/graph-utilities.js";
import {BidirectionalDijkstra} from "./bidirectional-dijkstra.js";

/**
 * Dijkstra's algorithm implementation for single-source shortest paths
 *
 * Finds shortest paths from a source node to all other nodes in a weighted graph
 * with non-negative edge weights using a priority queue for efficiency.
 */

/**
 * Find shortest paths from source to all reachable nodes using Dijkstra's algorithm
 */
export function dijkstra(
    graph: Graph,
    source: NodeId,
    options: DijkstraOptions = {},
): Map<NodeId, ShortestPathResult> {
    if (!graph.hasNode(source)) {
        throw new Error(`Source node ${String(source)} not found in graph`);
    }

    const distances = new Map<NodeId, number>();
    const previous = new Map<NodeId, NodeId | null>();
    const visited = new Set<NodeId>();
    const pq = new PriorityQueue<NodeId>();

    // Initialize distances
    for (const node of Array.from(graph.nodes())) {
        const distance = node.id === source ? 0 : Infinity;
        distances.set(node.id, distance);
        previous.set(node.id, null);
        pq.enqueue(node.id, distance);
    }

    while (!pq.isEmpty()) {
        const currentNode = pq.dequeue();
        if (currentNode === undefined) {
            break;
        }

        const currentDistance = distances.get(currentNode);
        if (currentDistance === undefined) {
            continue;
        }

        // Skip if already visited (can happen with priority queue updates)
        if (visited.has(currentNode)) {
            continue;
        }

        visited.add(currentNode);

        // Early termination if target reached
        if (options.target && currentNode === options.target) {
            break;
        }

        // Skip if this node is unreachable
        if (currentDistance === Infinity) {
            break;
        }

        // Check all neighbors
        for (const neighbor of Array.from(graph.neighbors(currentNode))) {
            if (visited.has(neighbor)) {
                continue;
            }

            const edge = graph.getEdge(currentNode, neighbor);
            if (!edge) {
                continue;
            }

            const edgeWeight = edge.weight ?? 1;

            if (edgeWeight < 0) {
                throw new Error("Dijkstra's algorithm does not support negative edge weights");
            }

            const tentativeDistance = currentDistance + edgeWeight;
            const neighborDistance = distances.get(neighbor);
            if (neighborDistance === undefined) {
                continue;
            }

            // Found a shorter path
            if (tentativeDistance < neighborDistance) {
                distances.set(neighbor, tentativeDistance);
                previous.set(neighbor, currentNode);
                // Add to priority queue with new distance
                pq.enqueue(neighbor, tentativeDistance);
            }
        }
    }

    // Build results
    const results = new Map<NodeId, ShortestPathResult>();

    for (const [nodeId, distance] of distances) {
        if (distance < Infinity) {
            const path = reconstructPath(nodeId, previous);
            results.set(nodeId, {
                distance,
                path,
                predecessor: new Map(previous),
            });
        }
    }

    return results;
}

/**
 * Find shortest path between two specific nodes using optimized Dijkstra's algorithm
 *
 * Uses bidirectional search by default for improved performance on point-to-point queries.
 * Automatically falls back to standard Dijkstra for very small graphs or when explicitly disabled.
 */
export function dijkstraPath(
    graph: Graph,
    source: NodeId,
    target: NodeId,
    options: DijkstraOptions = {},
): ShortestPathResult | null {
    if (!graph.hasNode(source)) {
        throw new Error(`Source node ${String(source)} not found in graph`);
    }

    if (!graph.hasNode(target)) {
        throw new Error(`Target node ${String(target)} not found in graph`);
    }

    // Special case: source equals target
    if (source === target) {
        return {
            distance: 0,
            path: [source],
            predecessor: new Map([[source, null]]),
        };
    }

    // Use bidirectional search by default for point-to-point queries
    // Only disable if explicitly requested or graph is very small (overhead dominates)
    const useBidirectional = options.bidirectional !== false && graph.nodeCount > 10;

    if (useBidirectional) {
        const biDijkstra = new BidirectionalDijkstra(graph);
        return biDijkstra.findShortestPath(source, target);
    }

    // Fallback to standard dijkstra
    const results = dijkstra(graph, source, {target});
    return results.get(target) ?? null;
}

/**
 * Single-source shortest paths with early termination optimization
 */
export function singleSourceShortestPath(
    graph: Graph,
    source: NodeId,
    cutoff?: number,
): Map<NodeId, number> {
    if (!graph.hasNode(source)) {
        throw new Error(`Source node ${String(source)} not found in graph`);
    }

    const distances = new Map<NodeId, number>();
    const visited = new Set<NodeId>();
    const pq = new PriorityQueue<NodeId>();

    // Initialize distances
    for (const node of Array.from(graph.nodes())) {
        const distance = node.id === source ? 0 : Infinity;
        distances.set(node.id, distance);
        pq.enqueue(node.id, distance);
    }

    while (!pq.isEmpty()) {
        const currentNode = pq.dequeue();
        if (currentNode === undefined) {
            break;
        }

        const currentDistance = distances.get(currentNode);
        if (currentDistance === undefined) {
            continue;
        }

        // Skip if already visited
        if (visited.has(currentNode)) {
            continue;
        }

        visited.add(currentNode);

        // Skip if unreachable or beyond cutoff
        if (currentDistance === Infinity || (cutoff !== undefined && currentDistance > cutoff)) {
            break;
        }

        // Check all neighbors
        for (const neighbor of Array.from(graph.neighbors(currentNode))) {
            if (visited.has(neighbor)) {
                continue;
            }

            const edge = graph.getEdge(currentNode, neighbor);
            if (!edge) {
                continue;
            }

            const edgeWeight = edge.weight ?? 1;
            const tentativeDistance = currentDistance + edgeWeight;
            const neighborDistance = distances.get(neighbor);
            if (neighborDistance === undefined) {
                continue;
            }

            // Found a shorter path
            if (tentativeDistance < neighborDistance) {
                distances.set(neighbor, tentativeDistance);
                pq.enqueue(neighbor, tentativeDistance);
            }
        }
    }

    // Filter out unreachable nodes and apply cutoff
    const result = new Map<NodeId, number>();

    for (const [nodeId, distance] of distances) {
        if (distance < Infinity && (cutoff === undefined || distance <= cutoff)) {
            result.set(nodeId, distance);
        }
    }

    return result;
}

/**
 * All-pairs shortest paths using repeated Dijkstra
 * Note: For dense graphs, consider Floyd-Warshall algorithm instead
 */
export function allPairsShortestPath(graph: Graph): Map<NodeId, Map<NodeId, number>> {
    const results = new Map<NodeId, Map<NodeId, number>>();

    for (const node of Array.from(graph.nodes())) {
        const distances = singleSourceShortestPath(graph, node.id);
        results.set(node.id, distances);
    }

    return results;
}


1	import type {Graph} from "../../core/graph.js";
2	import {PriorityQueue} from "../../data-structures/priority-queue.js";	2✔
3	import type {DijkstraOptions, NodeId, ShortestPathResult} from "../../types/index.js";
4	import {reconstructPath} from "../../utils/graph-utilities.js";	2✔
5	import {BidirectionalDijkstra} from "./bidirectional-dijkstra.js";	2✔
6
7	/**
8	* Dijkstra's algorithm implementation for single-source shortest paths
9	*
10	* Finds shortest paths from a source node to all other nodes in a weighted graph
11	* with non-negative edge weights using a priority queue for efficiency.
12	*/
13
14	/**
15	* Find shortest paths from source to all reachable nodes using Dijkstra's algorithm
16	*/
17	export function dijkstra(	2✔
18	graph: Graph,	35✔
19	source: NodeId,	35✔
20	options: DijkstraOptions = {},	35✔
21	): Map<NodeId, ShortestPathResult> {	35✔
22	if (!graph.hasNode(source)) {	35✔
23	throw new Error(`Source node ${String(source)} not found in graph`);	2✔
24	}	2✔
25
26	const distances = new Map<NodeId, number>();	33✔
27	const previous = new Map<NodeId, NodeId \| null>();	33✔
28	const visited = new Set<NodeId>();	33✔
29	const pq = new PriorityQueue<NodeId>();	33✔
30
31	// Initialize distances
32	for (const node of Array.from(graph.nodes())) {	35✔
33	const distance = node.id === source ? 0 : Infinity;	2,213✔
34	distances.set(node.id, distance);	2,213✔
35	previous.set(node.id, null);	2,213✔
36	pq.enqueue(node.id, distance);	2,213✔
37	}	2,213✔
38
39	while (!pq.isEmpty()) {	35✔
40	const currentNode = pq.dequeue();	420✔
41	if (currentNode === undefined) {	420!
42	break;	×
43	}	×
44
45	const currentDistance = distances.get(currentNode);	420✔
46	if (currentDistance === undefined) {	420!
47	continue;	×
48	}	×
49
50	// Skip if already visited (can happen with priority queue updates)
51	if (visited.has(currentNode)) {	420✔
52	continue;	132✔
53	}	132✔
54
55	visited.add(currentNode);	288✔
56
57	// Early termination if target reached
58	if (options.target && currentNode === options.target) {	420✔
59	break;	17✔
60	}	17✔
61
62	// Skip if this node is unreachable
63	if (currentDistance === Infinity) {	420✔
64	break;	2✔
65	}	2✔
66
67	// Check all neighbors
68	for (const neighbor of Array.from(graph.neighbors(currentNode))) {	420✔
69	if (visited.has(neighbor)) {	1,157✔
70	continue;	344✔
71	}	344✔
72
73	const edge = graph.getEdge(currentNode, neighbor);	813✔
74	if (!edge) {	1,157!
75	continue;	×
76	}	✔
77
78	const edgeWeight = edge.weight ?? 1;	1,157✔
79
80	if (edgeWeight < 0) {	1,157✔
81	throw new Error("Dijkstra's algorithm does not support negative edge weights");	1✔
82	}	1✔
83
84	const tentativeDistance = currentDistance + edgeWeight;	812✔
85	const neighborDistance = distances.get(neighbor);	812✔
86	if (neighborDistance === undefined) {	1,157!
87	continue;	×
88	}	✔
89
90	// Found a shorter path
91	if (tentativeDistance < neighborDistance) {	1,154✔
92	distances.set(neighbor, tentativeDistance);	597✔
93	previous.set(neighbor, currentNode);	597✔
94	// Add to priority queue with new distance
95	pq.enqueue(neighbor, tentativeDistance);	597✔
96	}	597✔
97	}	1,157✔
98	}	268✔
99
100	// Build results
101	const results = new Map<NodeId, ShortestPathResult>();	32✔
102
103	for (const [nodeId, distance] of distances) {	35✔
104	if (distance < Infinity) {	2,211✔
105	const path = reconstructPath(nodeId, previous);	530✔
106	results.set(nodeId, {	530✔
107	distance,	530✔
108	path,	530✔
109	predecessor: new Map(previous),	530✔
110	});	530✔
111	}	530✔
112	}	2,211✔
113
114	return results;	32✔
115	}	32✔
116
117	/**
118	* Find shortest path between two specific nodes using optimized Dijkstra's algorithm
119	*
120	* Uses bidirectional search by default for improved performance on point-to-point queries.
121	* Automatically falls back to standard Dijkstra for very small graphs or when explicitly disabled.
122	*/
123	export function dijkstraPath(	2✔
124	graph: Graph,	24✔
125	source: NodeId,	24✔
126	target: NodeId,	24✔
127	options: DijkstraOptions = {},	24✔
128	): ShortestPathResult \| null {	24✔
129	if (!graph.hasNode(source)) {	24✔
130	throw new Error(`Source node ${String(source)} not found in graph`);	1✔
131	}	1✔
132
133	if (!graph.hasNode(target)) {	24✔
134	throw new Error(`Target node ${String(target)} not found in graph`);	1✔
135	}	1✔
136
137	// Special case: source equals target
138	if (source === target) {	24✔
139	return {	1✔
140	distance: 0,	1✔
141	path: [source],	1✔
142	predecessor: new Map([[source, null]]),	1✔
143	};	1✔
144	}	1✔
145
146	// Use bidirectional search by default for point-to-point queries
147	// Only disable if explicitly requested or graph is very small (overhead dominates)
148	const useBidirectional = options.bidirectional !== false && graph.nodeCount > 10;	21✔
149
150	if (useBidirectional) {	24✔
151	const biDijkstra = new BidirectionalDijkstra(graph);	5✔
152	return biDijkstra.findShortestPath(source, target);	5✔
153	}	5✔
154
155	// Fallback to standard dijkstra
156	const results = dijkstra(graph, source, {target});	16✔
157	return results.get(target) ?? null;	24✔
158	}	24✔
159
160	/**
161	* Single-source shortest paths with early termination optimization
162	*/
163	export function singleSourceShortestPath(	2✔
164	graph: Graph,	12✔
165	source: NodeId,	12✔
166	cutoff?: number,	12✔
167	): Map<NodeId, number> {	12✔
168	if (!graph.hasNode(source)) {	12!
169	throw new Error(`Source node ${String(source)} not found in graph`);	×
170	}	×
171
172	const distances = new Map<NodeId, number>();	12✔
173	const visited = new Set<NodeId>();	12✔
174	const pq = new PriorityQueue<NodeId>();	12✔
175
176	// Initialize distances
177	for (const node of Array.from(graph.nodes())) {	12✔
178	const distance = node.id === source ? 0 : Infinity;	40✔
179	distances.set(node.id, distance);	40✔
180	pq.enqueue(node.id, distance);	40✔
181	}	40✔
182
183	while (!pq.isEmpty()) {	12✔
184	const currentNode = pq.dequeue();	48✔
185	if (currentNode === undefined) {	48!
186	break;	×
187	}	×
188
189	const currentDistance = distances.get(currentNode);	48✔
190	if (currentDistance === undefined) {	48!
191	continue;	×
192	}	×
193
194	// Skip if already visited
195	if (visited.has(currentNode)) {	48✔
196	continue;	14✔
197	}	14✔
198
199	visited.add(currentNode);	34✔
200
201	// Skip if unreachable or beyond cutoff
202	if (currentDistance === Infinity \|\| (cutoff !== undefined && currentDistance > cutoff)) {	48✔
203	break;	7✔
204	}	7✔
205
206	// Check all neighbors
207	for (const neighbor of Array.from(graph.neighbors(currentNode))) {	48✔
208	if (visited.has(neighbor)) {	38✔
209	continue;	18✔
210	}	18✔
211
212	const edge = graph.getEdge(currentNode, neighbor);	20✔
213	if (!edge) {	38!
214	continue;	×
215	}	✔
216
217	const edgeWeight = edge.weight ?? 1;	38!
218	const tentativeDistance = currentDistance + edgeWeight;	38✔
219	const neighborDistance = distances.get(neighbor);	38✔
220	if (neighborDistance === undefined) {	38!
221	continue;	×
222	}	✔
223
224	// Found a shorter path
225	if (tentativeDistance < neighborDistance) {	38✔
226	distances.set(neighbor, tentativeDistance);	19✔
227	pq.enqueue(neighbor, tentativeDistance);	19✔
228	}	19✔
229	}	38✔
230	}	27✔
231
232	// Filter out unreachable nodes and apply cutoff
233	const result = new Map<NodeId, number>();	12✔
234
235	for (const [nodeId, distance] of distances) {	12✔
236	if (distance < Infinity && (cutoff === undefined \|\| distance <= cutoff)) {	40✔
237	result.set(nodeId, distance);	27✔
238	}	27✔
239	}	40✔
240
241	return result;	12✔
242	}	12✔
243
244	/**
245	* All-pairs shortest paths using repeated Dijkstra
246	* Note: For dense graphs, consider Floyd-Warshall algorithm instead
247	*/
248	export function allPairsShortestPath(graph: Graph): Map<NodeId, Map<NodeId, number>> {	2✔
249	const results = new Map<NodeId, Map<NodeId, number>>();	3✔
250
251	for (const node of Array.from(graph.nodes())) {	3✔
252	const distances = singleSourceShortestPath(graph, node.id);	8✔
253	results.set(node.id, distances);	8✔
254	}	8✔
255
256	return results;	3✔
257	}	3✔
258

graphty-org / algorithms / 20198813057

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous