0
# Shortest Path Algorithms
1

2
Comprehensive collection of shortest path algorithms for finding optimal paths between nodes in weighted and unweighted graphs. rustworkx provides implementations of major shortest path algorithms optimized for performance with parallel processing support.
3

4
## Capabilities
5

6
### Dijkstra's Algorithm
7

8
Single-source shortest path algorithm for graphs with non-negative edge weights. Supports both single-target and all-targets modes with optional weight functions.
9

10
```python { .api }
11
def dijkstra_shortest_paths(graph, source: int, target: int = None, weight_fn = None, default_weight: float = 1.0, as_undirected: bool = False) -> dict:
12
    """
13
    Find shortest paths using Dijkstra's algorithm.
14
    
15
    Parameters:
16
    - graph: PyGraph or PyDiGraph to search
17
    - source (int): Source node index
18
    - target (int, optional): Target node index, if None finds paths to all nodes  
19
    - weight_fn (callable, optional): Function to extract edge weight
20
    - default_weight (float): Default edge weight if weight_fn not provided
21
    - as_undirected (bool): Treat directed graph as undirected
22
    
23
    Returns:
24
    dict: Mapping of target nodes to path lists
25
    """
26

27
def dijkstra_shortest_path_lengths(graph, node: int, edge_cost_fn, goal: int = None) -> dict:
28
    """
29
    Compute shortest path lengths using Dijkstra's algorithm.
30
    
31
    Parameters:
32
    - graph: Input graph
33
    - node (int): Source node index
34
    - edge_cost_fn (callable): Function returning edge cost as float
35
    - goal (int, optional): Target node, returns single entry if specified
36
    
37
    Returns:
38
    dict: Mapping of target nodes to path lengths
39
    """
40

41
def all_pairs_dijkstra_shortest_paths(graph, edge_cost_fn):
42
    """
43
    All-pairs shortest paths using Dijkstra's algorithm.
44
    Multithreaded execution for improved performance.
45
    
46
    Parameters:
47
    - graph: Input graph
48
    - edge_cost_fn (callable): Function returning edge cost as float
49
    
50
    Returns:  
51
    AllPairsPathMapping: Nested mapping of source -> target -> path
52
    """
53

54
def all_pairs_dijkstra_path_lengths(graph, edge_cost_fn):
55
    """
56
    All-pairs shortest path lengths using Dijkstra's algorithm.
57
    
58
    Parameters:
59
    - graph: Input graph  
60
    - edge_cost_fn (callable): Function returning edge cost as float
61
    
62
    Returns:
63
    AllPairsPathLengthMapping: Nested mapping of source -> target -> length
64
    """
65
```
66

67
### Bellman-Ford Algorithm
68

69
Single-source shortest path algorithm supporting negative edge weights. Detects negative cycles and provides comprehensive error handling.
70

71
```python { .api }
72
def bellman_ford_shortest_paths(graph, source: int, target: int = None, weight_fn = None, default_weight: float = 1.0, as_undirected: bool = False):
73
    """
74
    Find shortest paths using Bellman-Ford algorithm.
75
    Supports negative edge weights and detects negative cycles.
76
    
77
    Parameters:
78
    - graph: PyGraph or PyDiGraph to search
79
    - source (int): Source node index
80
    - target (int, optional): Target node index
81
    - weight_fn (callable, optional): Function to extract edge weight
82
    - default_weight (float): Default edge weight
83
    - as_undirected (bool): Treat directed graph as undirected
84
    
85
    Returns:
86
    PathMapping: Mapping of target nodes to paths
87
    
88
    Raises:
89
    NegativeCycle: When negative cycle is detected
90
    """
91

92
def bellman_ford_shortest_path_lengths(graph, node: int, edge_cost_fn, goal: int = None):
93
    """
94
    Compute shortest path lengths using Bellman-Ford algorithm.
95
    
96
    Parameters:
97
    - graph: Input graph
98
    - node (int): Source node index  
99
    - edge_cost_fn (callable): Function returning edge cost (can be negative)
100
    - goal (int, optional): Target node
101
    
102
    Returns:
103
    PathLengthMapping: Mapping of target nodes to path lengths
104
    
105
    Raises:
106
    NegativeCycle: When negative cycle is detected
107
    """
108

109
def all_pairs_bellman_ford_shortest_paths(graph, edge_cost_fn):
110
    """
111
    All-pairs shortest paths using Bellman-Ford algorithm.
112
    
113
    Parameters:
114
    - graph: Input graph
115
    - edge_cost_fn (callable): Function returning edge cost
116
    
117
    Returns:
118
    AllPairsPathMapping: Nested mapping of source -> target -> path
119
    
120
    Raises:
121
    NegativeCycle: When negative cycle is detected
122
    """
123

124
def all_pairs_bellman_ford_path_lengths(graph, edge_cost_fn):
125
    """
126
    All-pairs shortest path lengths using Bellman-Ford algorithm.
127
    
128
    Parameters:
129
    - graph: Input graph
130
    - edge_cost_fn (callable): Function returning edge cost
131
    
132
    Returns:
133
    AllPairsPathLengthMapping: Nested mapping of source -> target -> length
134
    
135
    Raises:
136
    NegativeCycle: When negative cycle is detected
137
    """
138
```
139

140
### Floyd-Warshall Algorithm
141

142
All-pairs shortest path algorithm particularly effective for dense graphs. Supports parallel execution and multiple output formats.
143

144
```python { .api }
145
def floyd_warshall(graph, weight_fn = None, default_weight: float = 1.0, parallel_threshold: int = 300):
146
    """
147
    All-pairs shortest paths using Floyd-Warshall algorithm.
148
    
149
    Parameters:
150
    - graph: Input graph
151
    - weight_fn (callable, optional): Function to extract edge weight
152
    - default_weight (float): Default edge weight
153
    - parallel_threshold (int): Node count threshold for parallel execution
154
    
155
    Returns:
156
    AllPairsPathLengthMapping: Nested mapping of path lengths
157
    """
158

159
def floyd_warshall_numpy(graph, weight_fn = None, default_weight: float = 1.0, parallel_threshold: int = 300):
160
    """
161
    Floyd-Warshall algorithm returning NumPy distance matrix.
162
    
163
    Parameters:
164
    - graph: Input graph
165
    - weight_fn (callable, optional): Function to extract edge weight  
166
    - default_weight (float): Default edge weight
167
    - parallel_threshold (int): Node count threshold for parallel execution
168
    
169
    Returns:
170
    numpy.ndarray: Distance matrix with np.inf for unreachable pairs
171
    """
172

173
def floyd_warshall_successor_and_distance(graph, weight_fn = None, default_weight: float = 1.0, parallel_threshold: int = 300):
174
    """
175
    Floyd-Warshall returning both distance and successor matrices.
176
    
177
    Parameters:
178
    - graph: Input graph (PyDiGraph only)
179
    - weight_fn (callable, optional): Function to extract edge weight
180
    - default_weight (float): Default edge weight  
181
    - parallel_threshold (int): Node count threshold for parallel execution
182
    
183
    Returns:
184
    Tuple[numpy.ndarray, numpy.ndarray]: (distance_matrix, successor_matrix)
185
    """
186
```
187

188
### A* Algorithm
189

190
Heuristic shortest path algorithm using estimated costs to guide search toward target node. Optimal when heuristic is admissible.
191

192
```python { .api }
193
def astar_shortest_path(graph, node: int, goal_fn, edge_cost_fn, estimate_cost_fn):
194
    """
195
    A* shortest path algorithm with heuristic guidance.
196
    
197
    Parameters:
198
    - graph: Input graph
199
    - node (int): Starting node index
200
    - goal_fn (callable): Function returning True for goal nodes
201
    - edge_cost_fn (callable): Function returning non-negative edge cost
202
    - estimate_cost_fn (callable): Heuristic function returning estimated cost to goal
203
    
204
    Returns:
205
    NodeIndices: List of node indices forming shortest path
206
    """
207
```
208

209
### Specialized Path Functions
210

211
Additional path-finding utilities for specific use cases and path enumeration.
212

213
```python { .api }
214
def all_simple_paths(graph, from_: int, to, min_depth: int = None, cutoff: int = None) -> list:
215
    """
216
    Find all simple paths between nodes (no repeated nodes).
217
    
218
    Parameters:
219
    - graph: Input graph
220
    - from_ (int): Source node index
221
    - to (int or list): Target node(s)
222
    - min_depth (int, optional): Minimum path length
223
    - cutoff (int, optional): Maximum path length
224
    
225
    Returns:
226
    list: List of paths, each path is list of node indices
227
    """
228

229
def all_shortest_paths(graph, source: int, target: int, weight_fn = None, default_weight: float = 1.0, as_undirected: bool = False) -> list:
230
    """
231
    Find all shortest paths between two specific nodes.
232
    
233
    Parameters:
234
    - graph: Input graph
235
    - source (int): Source node index
236
    - target (int): Target node index
237
    - weight_fn (callable, optional): Function to extract edge weight
238
    - default_weight (float): Default edge weight
239
    - as_undirected (bool): Treat directed graph as undirected
240
    
241
    Returns:
242
    list: List of shortest paths (each path is list of node indices)
243
    """
244

245
def single_source_all_shortest_paths(graph, source: int, weight_fn = None, default_weight: float = 1.0, as_undirected: bool = False) -> dict:
246
    """
247
    All shortest paths from single source to all other nodes.
248
    
249
    Parameters:
250
    - graph: Input graph
251
    - source (int): Source node index
252
    - weight_fn (callable, optional): Function to extract edge weight
253
    - default_weight (float): Default edge weight
254
    - as_undirected (bool): Treat directed graph as undirected
255
    
256
    Returns:
257
    dict: Mapping of target nodes to lists of shortest paths
258
    """
259

260
def k_shortest_path_lengths(graph, start: int, k: int, edge_cost, goal: int = None) -> dict:
261
    """
262
    Compute lengths of k-th shortest paths.
263
    
264
    Parameters:
265
    - graph: Input graph
266
    - start (int): Source node index
267
    - k (int): Which shortest path to find (1st, 2nd, etc.)
268
    - edge_cost (callable): Function returning edge cost
269
    - goal (int, optional): Target node
270
    
271
    Returns:
272
    dict: Mapping of destination nodes to k-th shortest path length
273
    """
274

275
def has_path(graph, source: int, target: int, as_undirected: bool = False) -> bool:
276
    """
277
    Check if path exists between two nodes.
278
    
279
    Parameters:
280
    - graph: Input graph
281
    - source (int): Source node index
282
    - target (int): Target node index
283
    - as_undirected (bool): Treat directed graph as undirected
284
    
285
    Returns:
286
    bool: True if path exists, False otherwise
287
    """
288
```
289

290
### Distance and Connectivity Utilities
291

292
Functions for computing graph distances and analyzing connectivity patterns.
293

294
```python { .api }
295
def distance_matrix(graph, parallel_threshold: int = 300, as_undirected: bool = False, null_value: float = 0.0):
296
    """
297
    Compute unweighted distance matrix (each edge has distance 1).
298
    
299
    Parameters:
300
    - graph: Input graph
301
    - parallel_threshold (int): Node count for parallel execution
302
    - as_undirected (bool): Treat directed graph as undirected
303
    - null_value (float): Value for absent edges
304
    
305
    Returns:
306
    numpy.ndarray: Distance matrix
307
    """
308

309
def unweighted_average_shortest_path_length(graph, parallel_threshold: int = 300, disconnected: bool = False) -> float:
310
    """
311
    Average shortest path length with unweighted edges.
312
    
313
    Parameters:
314
    - graph: Input graph
315
    - parallel_threshold (int): Node count for parallel execution  
316
    - disconnected (bool): Include only connected pairs if True
317
    
318
    Returns:
319
    float: Average shortest path length
320
    """
321

322
def num_shortest_paths_unweighted(graph, source: int):
323
    """
324
    Count unweighted shortest paths from source node.
325
    
326
    Parameters:
327
    - graph: Input graph
328
    - source (int): Source node index
329
    
330
    Returns:
331
    NodesCountMapping: Mapping of target nodes to path counts
332
    """
333
```
334

335
## Usage Examples
336

337
### Basic Shortest Path Finding
338

339
```python
340
import rustworkx as rx
341

342
# Create weighted graph
343
graph = rx.PyGraph()
344
nodes = graph.add_nodes_from(['A', 'B', 'C', 'D'])
345
graph.add_edges_from([
346
    (nodes[0], nodes[1], 4.0),
347
    (nodes[1], nodes[2], 2.0), 
348
    (nodes[2], nodes[3], 3.0),
349
    (nodes[0], nodes[3], 10.0)
350
])
351

352
# Find shortest paths from node 0
353
paths = rx.dijkstra_shortest_paths(graph, nodes[0])
354
print(f"Paths from A: {paths}")
355

356
# Get only path lengths
357
lengths = rx.dijkstra_shortest_path_lengths(
358
    graph, nodes[0], 
359
    edge_cost_fn=lambda x: x
360
)
361
print(f"Path lengths: {lengths}")
362
```
363

364
### Handling Negative Weights
365

366
```python
367
# Graph with negative weights
368
digraph = rx.PyDiGraph()
369
nodes = digraph.add_nodes_from(['S', 'A', 'B', 'T'])
370
digraph.add_edges_from([
371
    (nodes[0], nodes[1], 1.0),
372
    (nodes[1], nodes[2], -3.0),  # Negative weight
373
    (nodes[2], nodes[3], 2.0),
374
    (nodes[0], nodes[3], 5.0)
375
])
376

377
try:
378
    paths = rx.bellman_ford_shortest_paths(
379
        digraph, nodes[0],
380
        weight_fn=lambda x: x
381
    )
382
    print(f"Shortest paths: {paths}")
383
except rx.NegativeCycle as e:
384
    print(f"Negative cycle detected: {e}")
385
```
386

387
### A* Pathfinding with Heuristic
388

389
```python
390
# Grid graph for A* demonstration
391
def manhattan_distance(node_data, target_pos):
392
    """Manhattan distance heuristic."""
393
    x1, y1 = node_data
394
    x2, y2 = target_pos  
395
    return abs(x1 - x2) + abs(y1 - y2)
396

397
grid = rx.generators.grid_graph(5, 5)
398
target_node = 24  # Bottom-right corner
399
target_pos = (4, 4)
400

401
path = rx.astar_shortest_path(
402
    grid,
403
    node=0,  # Top-left corner
404
    goal_fn=lambda node: node == target_node,
405
    edge_cost_fn=lambda edge: 1.0,
406
    estimate_cost_fn=lambda node: manhattan_distance(node, target_pos)
407
)
408
print(f"A* path: {path}")
409
```
410

411
### All-Pairs Shortest Paths
412

413
```python
414
# Compute all-pairs shortest paths
415
all_paths = rx.all_pairs_dijkstra_shortest_paths(
416
    graph, 
417
    edge_cost_fn=lambda x: x
418
)
419

420
# Access specific path
421
path_0_to_3 = all_paths[nodes[0]][nodes[3]]
422
print(f"Path from A to D: {path_0_to_3}")
423

424
# Get distance matrix for analysis
425
distances = rx.floyd_warshall_numpy(graph, weight_fn=lambda x: x)
426
print(f"Distance matrix:\n{distances}")
427
```