mirror of
https://github.com/hanzoai/skills.git
synced 2026-11-19 00:47:36 +00:00
hanzoskills.com/llms.txt now opens with the install line, the API reference index and the company index, so an agent that lands on any one of the three can find the rest. robots.txt claimed 537 documents while llms.txt counts 920. The number is gone from robots.txt; llms.txt derives it. public/ is regenerated from scripts/site.py, which it had fallen behind: the copy-prompt menu and agent bar were in the generator and not in the committed pages. tests/site.mjs passes against the result. Co-authored-by: Hanzo Dev <[email protected]>
805 lines
34 KiB
HTML
805 lines
34 KiB
HTML
<!doctype html>
|
||
<html lang="en"><head>
|
||
<meta charset="utf-8"><meta name="viewport" content="width=device-width,initial-scale=1">
|
||
<title>shortest-path-algorithms</title>
|
||
<meta name="color-scheme" content="dark">
|
||
<style>
|
||
/* Committed to one visual world: a dark instrument panel. No light variant —
|
||
the dot field and the hairline rules only read on black, and a naive
|
||
inversion would wash both out. Every colour is painted explicitly so the page
|
||
never borrows a host background. */
|
||
@font-face{font-family:'Zen';src:url('/fonts/Zen-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
|
||
@font-face{font-family:'Zen';src:url('/fonts/Zen-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
|
||
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
|
||
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
|
||
@font-face{font-family:'Zen Pixel Square';src:url('/fonts/ZenPixel-Square.woff2') format('woff2');font-style:normal;font-display:swap}
|
||
|
||
:root{
|
||
--ink:#f4f4f2; --soft:#9c9c98; --faint:#6a6a66; --ground:#000; --panel:#0a0a0a;
|
||
--line:#232323; --line-hi:#3a3a3a; --accent:#f4f4f2;
|
||
--font-zen-sans:'Zen',-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif;
|
||
--font-zen-mono:'Zen Mono',ui-monospace,"SF Mono",SFMono-Regular,Menlo,Consolas,monospace;
|
||
--font-zen-pixel-square:'Zen Pixel Square',monospace;
|
||
--mono:var(--font-zen-mono);
|
||
--sans:var(--font-zen-sans);
|
||
/* Controls are pills and surfaces are soft, as on hanzo.ai. */
|
||
--r:999px; --r-soft:14px;
|
||
}
|
||
*{box-sizing:border-box}
|
||
html{-webkit-text-size-adjust:100%}
|
||
body{margin:0;background:var(--ground);color:var(--ink);font-family:var(--sans);
|
||
font-size:16px;line-height:1.65;-webkit-font-smoothing:antialiased}
|
||
.wrap{max-width:60rem;margin:0 auto;padding:0 1.75rem}
|
||
|
||
/* The dot field. A halftone made of one repeating radial-gradient, faded out
|
||
along the diagonal by a mask so it reads as a wave rather than wallpaper. */
|
||
/* No overflow clip here: the dot field is inset to the box already, and a clip
|
||
would cut off the copy-prompt menu. */
|
||
.hero{position:relative;border-bottom:1px solid var(--line)}
|
||
.hero::before{content:"";position:absolute;inset:0;
|
||
background-image:radial-gradient(var(--line-hi) 1px, transparent 1px);
|
||
background-size:7px 7px;
|
||
-webkit-mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
|
||
mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
|
||
pointer-events:none}
|
||
.hero .wrap{position:relative;padding-top:5.5rem;padding-bottom:4rem}
|
||
|
||
nav{border-bottom:1px solid var(--line)}
|
||
nav .in{max-width:60rem;margin:0 auto;padding:1.1rem 1.75rem;display:flex;
|
||
justify-content:space-between;align-items:center;gap:1rem}
|
||
.brand{font-family:var(--mono);font-size:.85rem;letter-spacing:.14em;
|
||
text-transform:uppercase;color:var(--ink);text-decoration:none;
|
||
display:inline-flex;align-items:center;gap:.6rem}
|
||
.brand i{font-style:normal;color:var(--faint)}
|
||
.mark{width:1.15em;height:1.15em;display:block;flex:0 0 auto}
|
||
nav a.up{font-family:var(--mono);font-size:.72rem;letter-spacing:.14em;
|
||
text-transform:uppercase;color:var(--soft);text-decoration:none}
|
||
nav a.up:hover{color:var(--ink)}
|
||
|
||
h1{font-family:var(--mono);font-size:clamp(2rem,5.4vw,3.4rem);line-height:1.12;
|
||
letter-spacing:-.02em;margin:0 0 1.1rem;font-weight:500;text-wrap:balance}
|
||
h1 em{font-style:normal;color:var(--faint)}
|
||
.lede{color:var(--soft);font-size:1.05rem;max-width:52ch;margin:0 0 2.25rem}
|
||
|
||
.btns{display:flex;flex-wrap:wrap;gap:.7rem;margin:0 0 .5rem;align-items:center}
|
||
.btn{display:inline-flex;align-items:center;gap:.5rem;font-family:var(--mono);
|
||
font-size:.72rem;letter-spacing:.14em;text-transform:uppercase;
|
||
padding:.8rem 1.4rem;border:1px solid var(--line-hi);border-radius:var(--r);
|
||
color:var(--ink);text-decoration:none;background:transparent;cursor:pointer;
|
||
line-height:1.2;font-weight:400}
|
||
.btn:hover{background:#141414;text-decoration:none;border-color:var(--soft)}
|
||
.btn.solid{background:var(--ink);color:#000;border-color:var(--ink)}
|
||
.btn.solid:hover{background:#d8d8d4}
|
||
.btn .chev{width:.7em;height:.7em;flex:0 0 auto;transition:transform .15s ease}
|
||
.btn[aria-expanded="true"] .chev{transform:rotate(180deg)}
|
||
|
||
/* Copy-prompt selector. Each row copies the prompt for its own target. */
|
||
.copy{position:relative;display:inline-flex}
|
||
.menu{position:absolute;top:calc(100% + .5rem);left:0;z-index:20;min-width:21rem;
|
||
background:var(--panel);border:1px solid var(--line-hi);border-radius:var(--r-soft);
|
||
padding:.4rem;display:flex;flex-direction:column;
|
||
box-shadow:0 12px 32px rgba(0,0,0,.75)}
|
||
.menu[hidden]{display:none}
|
||
.mi{display:flex;align-items:center;gap:.7rem;width:100%;text-align:left;
|
||
padding:.62rem .8rem;border:0;border-radius:calc(var(--r-soft) - .35rem);
|
||
background:transparent;color:var(--ink);font-family:var(--mono);font-size:.76rem;
|
||
letter-spacing:.04em;text-decoration:none;cursor:pointer;line-height:1.3;
|
||
white-space:nowrap}
|
||
.mi:hover,.mi:focus-visible{background:#181818;outline:none}
|
||
.mi .mark{width:1.05rem;height:1.05rem;color:var(--soft)}
|
||
.mi:hover .mark{color:var(--ink)}
|
||
.mi u{margin-left:auto;color:var(--faint);text-decoration:none;font-size:.68rem;
|
||
letter-spacing:.1em;text-transform:uppercase}
|
||
|
||
/* Works-with bar: one scrolling row, name and mark per agent. */
|
||
.strip{border-bottom:1px solid var(--line);background:var(--panel)}
|
||
.strip .in{max-width:60rem;margin:0 auto;padding:.9rem 1.75rem;display:flex;
|
||
align-items:center;gap:1.25rem;font-family:var(--mono);font-size:.72rem;
|
||
letter-spacing:.1em;text-transform:uppercase;color:var(--faint)}
|
||
.strip b{color:var(--soft);font-weight:400;flex:0 0 auto;
|
||
border-right:1px solid var(--line);padding-right:1.25rem;align-self:stretch;
|
||
display:flex;align-items:center}
|
||
.bar{display:flex;align-items:center;gap:.5rem;flex:1 1 auto;min-width:0;
|
||
overflow-x:auto;scrollbar-width:none;scroll-snap-type:x proximity;
|
||
-webkit-overflow-scrolling:touch;
|
||
-webkit-mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent);
|
||
mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent)}
|
||
.bar::-webkit-scrollbar{display:none}
|
||
.agent{display:inline-flex;align-items:center;gap:.45rem;flex:0 0 auto;
|
||
padding:.4rem .85rem;border:1px solid var(--line);border-radius:var(--r);
|
||
color:var(--soft);white-space:nowrap;scroll-snap-align:start;
|
||
text-decoration:none;background:var(--ground)}
|
||
.agent:hover{color:var(--ink);border-color:var(--line-hi);text-decoration:none}
|
||
.agent .mark{width:.95rem;height:.95rem}
|
||
|
||
h2{font-family:var(--mono);font-size:1.1rem;letter-spacing:-.01em;margin:2.75rem 0 .75rem;font-weight:500}
|
||
h3{font-size:1rem;margin:2rem 0 .5rem;font-weight:600}
|
||
h4,h5,h6{font-size:.94rem;margin:1.5rem 0 .5rem;font-weight:600}
|
||
p{margin:0 0 1rem;max-width:70ch}
|
||
ul,ol{margin:0 0 1rem;padding-left:1.35rem;max-width:70ch}
|
||
li{margin:.22rem 0}
|
||
a{color:var(--ink);text-decoration:underline;text-underline-offset:3px;
|
||
text-decoration-color:var(--line-hi)}
|
||
a:hover{text-decoration-color:var(--ink)}
|
||
a:focus-visible{outline:1px solid var(--ink);outline-offset:3px}
|
||
code{font-family:var(--mono);font-size:.85em;background:var(--panel);
|
||
border:1px solid var(--line);border-radius:5px;padding:.1em .36em}
|
||
pre{background:var(--panel);border:1px solid var(--line);padding:1rem 1.1rem;
|
||
border-radius:var(--r-soft);overflow-x:auto;margin:0 0 1.25rem}
|
||
pre code{background:none;border:0;padding:0;font-size:.82rem;line-height:1.7}
|
||
blockquote{margin:0 0 1rem;padding-left:1rem;border-left:1px solid var(--line-hi);color:var(--soft)}
|
||
hr{border:0;border-top:1px solid var(--line);margin:2.5rem 0}
|
||
table{border-collapse:collapse;width:100%;margin:0 0 1.25rem;font-size:.92rem;
|
||
display:block;overflow-x:auto}
|
||
th,td{border:1px solid var(--line);padding:.5rem .7rem;text-align:left}
|
||
|
||
.curl{display:block;background:var(--panel);border:1px solid var(--line);
|
||
border-radius:var(--r-soft);padding:.95rem 1.1rem;font-family:var(--mono);
|
||
font-size:.8rem;color:var(--soft);overflow-x:auto;margin:0 0 2.5rem;
|
||
white-space:pre;line-height:1.9}
|
||
.curl b{color:var(--ink);font-weight:400}
|
||
.curl i{font-style:normal;color:var(--faint)}
|
||
|
||
/* index */
|
||
#q{width:100%;padding:.85rem 1.2rem;font-family:var(--mono);font-size:.85rem;color:var(--ink);
|
||
background:var(--panel);border:1px solid var(--line);border-radius:var(--r);margin:0 0 .6rem}
|
||
#q::placeholder{color:var(--faint);text-transform:uppercase;letter-spacing:.1em;font-size:.72rem}
|
||
#q:focus{outline:none;border-color:var(--soft)}
|
||
#count{color:var(--faint);font-family:var(--mono);font-size:.72rem;letter-spacing:.1em;
|
||
text-transform:uppercase;margin:0 0 2rem}
|
||
.cat{margin:2.5rem 0 .5rem;font-family:var(--mono);font-size:.7rem;letter-spacing:.16em;
|
||
text-transform:uppercase;color:var(--faint);border-bottom:1px solid var(--line);
|
||
padding-bottom:.45rem}
|
||
.row{display:block;padding:.6rem .9rem;margin:0 -.9rem;border-bottom:1px solid var(--line);
|
||
border-radius:var(--r-soft);text-decoration:none}
|
||
.row:hover{background:#0a0a0a}
|
||
.nm{font-family:var(--mono);font-size:.84rem;color:var(--ink);display:block}
|
||
.ds{color:var(--soft);font-size:.9rem;display:block;margin-top:.12rem}
|
||
footer{margin-top:4rem;padding:2rem 0 4rem;border-top:1px solid var(--line);
|
||
color:var(--faint);font-size:.85rem}
|
||
footer a{color:var(--soft)}
|
||
.fmap{display:grid;gap:1.75rem;grid-template-columns:repeat(auto-fit,minmax(11rem,1fr));
|
||
margin:0 0 2rem;font-size:.85rem}
|
||
.fmap b{display:block;font-family:var(--mono);font-size:.68rem;letter-spacing:.16em;
|
||
text-transform:uppercase;color:var(--faint);font-weight:400;margin:0 0 .6rem;
|
||
border-bottom:1px solid var(--line);padding-bottom:.4rem}
|
||
.fmap a{display:inline-block;color:var(--ink);text-decoration:none;margin:.3rem .35rem 0 0}
|
||
.fmap a:hover{text-decoration:underline}
|
||
.fmap div{color:var(--faint);line-height:1.5}
|
||
.fend{border-top:1px solid var(--line);padding-top:1.25rem;font-size:.82rem}
|
||
|
||
@media (max-width:640px){
|
||
.hero .wrap{padding-top:3.25rem;padding-bottom:2.75rem}
|
||
.btns{gap:.5rem}
|
||
.btn{padding:.75rem 1.15rem;font-size:.68rem}
|
||
.copy,.copy .btn{width:100%;justify-content:center}
|
||
.menu{left:0;right:0;min-width:0}
|
||
.strip .in{flex-direction:column;align-items:flex-start;gap:.6rem;padding:.9rem 1.75rem}
|
||
.strip b{border-right:0;padding-right:0}
|
||
.bar{width:100%}
|
||
}
|
||
</style>
|
||
<link rel="alternate" type="text/markdown" href="/shortest-path-algorithms.md">
|
||
|
||
<link rel="icon" href="/favicon.svg">
|
||
<link rel="canonical" href="https://hanzoskills.com/shortest-path-algorithms">
|
||
</head>
|
||
<!-- Reading this with a machine? Every page here is also plain markdown.
|
||
This one: https://hanzoskills.com/shortest-path-algorithms.md
|
||
Index: https://hanzoskills.com/llms.txt
|
||
Corpus: https://hanzoskills.com/all.md
|
||
Append .md to any path for the markdown twin. -->
|
||
<body>
|
||
<nav><div class="in">
|
||
<a class="brand" href="/"><svg class="mark" viewBox="0 0 67 67" fill="currentColor" aria-hidden="true"><path d="M22.21 67V44.6369H0V67H22.21Z"/><path d="M66.7038 22.3184H22.2534L0.0878906 44.6367H44.4634L66.7038 22.3184Z"/><path d="M22.21 0H0V22.3184H22.21V0Z"/><path d="M66.7198 0H44.5098V22.3184H66.7198V0Z"/><path d="M66.7198 67V44.6369H44.5098V67H66.7198Z"/></svg> HANZO<i>SKILLS</i></a>
|
||
<a class="up" href="/">All skills</a>
|
||
</div></nav>
|
||
|
||
<div class="wrap">
|
||
<h1>shortest-path-algorithms</h1><p class="lede">Dijkstra, Bellman-Ford, Floyd-Warshall, and A* algorithms for finding shortest paths in weighted graphs with various constraints</p><h1>Shortest Path Algorithms</h1>
|
||
<p><strong>Last Updated</strong>: 2025-10-25</p>
|
||
<h2>When to Use This Skill</h2>
|
||
<p><strong>Activate when</strong>:</p>
|
||
<ul><li>Finding shortest paths in weighted graphs</li><li>Route planning and navigation</li><li>Network routing protocols</li><li>Optimizing delivery routes</li><li>Handling negative edge weights</li><li>Computing all-pairs shortest paths</li><li>Using heuristics for faster pathfinding (A*)</li></ul>
|
||
<p><strong>Prerequisites</strong>: <code>graph-theory-fundamentals.md</code>, <code>graph-data-structures.md</code>, <code>graph-traversal-algorithms.md</code></p>
|
||
<p><strong>Related Skills</strong>: <code>minimum-spanning-tree.md</code>, <code>network-flow-algorithms.md</code>, <code>graph-applications.md</code></p>
|
||
<hr>
|
||
<h2>Core Algorithms</h2>
|
||
<h3>1. Dijkstra's Algorithm</h3>
|
||
<p><strong>Concept</strong>: Greedy algorithm for single-source shortest paths with non-negative weights</p>
|
||
<p><strong>Properties</strong>:</p>
|
||
<ul><li><strong>Time</strong>: O((V + E) log V) with binary heap, O(V²) with array</li><li><strong>Space</strong>: O(V) for distances and priority queue</li><li><strong>Constraint</strong>: Requires non-negative edge weights</li><li><strong>Finds</strong>: Shortest paths from source to all vertices</li></ul>
|
||
<pre><code class="lang-python">import heapq
|
||
from typing import Dict, List, Tuple, Optional
|
||
from dataclasses import dataclass
|
||
import math
|
||
|
||
@dataclass
|
||
class DijkstraResult:
|
||
"""Results from Dijkstra's algorithm"""
|
||
distances: Dict[int, float]
|
||
parents: Dict[int, Optional[int]]
|
||
|
||
def get_path(self, target: int) -> Optional[List[int]]:
|
||
"""Reconstruct shortest path to target"""
|
||
if target not in self.parents:
|
||
return None
|
||
|
||
path = []
|
||
current = target
|
||
|
||
while current is not None:
|
||
path.append(current)
|
||
current = self.parents[current]
|
||
|
||
return list(reversed(path))
|
||
|
||
def dijkstra(graph: 'WeightedGraph', source: int) -> DijkstraResult:
|
||
"""
|
||
Dijkstra's shortest path algorithm
|
||
|
||
Args:
|
||
graph: Weighted graph (adjacency list with weights)
|
||
source: Starting vertex
|
||
|
||
Returns:
|
||
DijkstraResult with distances and parent pointers
|
||
"""
|
||
# Initialize distances to infinity
|
||
distances = {v: math.inf for v in range(graph.num_vertices)}
|
||
distances[source] = 0
|
||
|
||
# Parent pointers for path reconstruction
|
||
parents = {source: None}
|
||
|
||
# Priority queue: (distance, vertex)
|
||
pq = [(0, source)]
|
||
visited = set()
|
||
|
||
while pq:
|
||
dist_u, u = heapq.heappop(pq)
|
||
|
||
if u in visited:
|
||
continue
|
||
|
||
visited.add(u)
|
||
|
||
# Relaxation: Update distances to neighbors
|
||
for edge in graph.adj[u]:
|
||
v = edge.dest
|
||
weight = edge.weight
|
||
|
||
if v in visited:
|
||
continue
|
||
|
||
new_dist = distances[u] + weight
|
||
|
||
if new_dist < distances[v]:
|
||
distances[v] = new_dist
|
||
parents[v] = u
|
||
heapq.heappush(pq, (new_dist, v))
|
||
|
||
return DijkstraResult(distances, parents)
|
||
|
||
# Example usage
|
||
from graph_data_structures import WeightedGraph
|
||
|
||
graph = WeightedGraph(5, directed=False)
|
||
graph.add_edge(0, 1, 4)
|
||
graph.add_edge(0, 2, 1)
|
||
graph.add_edge(2, 1, 2)
|
||
graph.add_edge(1, 3, 1)
|
||
graph.add_edge(2, 3, 5)
|
||
graph.add_edge(3, 4, 3)
|
||
|
||
result = dijkstra(graph, source=0)
|
||
path = result.get_path(4)
|
||
print(f"Shortest path 0→4: {path}") # [0, 2, 1, 3, 4]
|
||
print(f"Distance: {result.distances[4]}") # 7.0</code></pre>
|
||
<p><strong>Optimized Dijkstra with Early Termination</strong>:</p>
|
||
<pre><code class="lang-python">def dijkstra_single_target(graph: 'WeightedGraph',
|
||
source: int,
|
||
target: int) -> Tuple[float, List[int]]:
|
||
"""
|
||
Dijkstra with early termination when target is reached
|
||
|
||
More efficient when only one shortest path is needed
|
||
"""
|
||
distances = {v: math.inf for v in range(graph.num_vertices)}
|
||
distances[source] = 0
|
||
parents = {source: None}
|
||
|
||
pq = [(0, source)]
|
||
visited = set()
|
||
|
||
while pq:
|
||
dist_u, u = heapq.heappop(pq)
|
||
|
||
# Early termination
|
||
if u == target:
|
||
path = []
|
||
current = target
|
||
while current is not None:
|
||
path.append(current)
|
||
current = parents[current]
|
||
return dist_u, list(reversed(path))
|
||
|
||
if u in visited:
|
||
continue
|
||
|
||
visited.add(u)
|
||
|
||
for edge in graph.adj[u]:
|
||
v = edge.dest
|
||
new_dist = distances[u] + edge.weight
|
||
|
||
if new_dist < distances[v]:
|
||
distances[v] = new_dist
|
||
parents[v] = u
|
||
heapq.heappush(pq, (new_dist, v))
|
||
|
||
return math.inf, [] # Target not reachable</code></pre>
|
||
<h3>2. Bellman-Ford Algorithm</h3>
|
||
<p><strong>Concept</strong>: Dynamic programming approach that handles negative weights</p>
|
||
<p><strong>Properties</strong>:</p>
|
||
<ul><li><strong>Time</strong>: O(V × E)</li><li><strong>Space</strong>: O(V) for distances</li><li><strong>Constraint</strong>: Detects negative cycles</li><li><strong>Finds</strong>: Shortest paths even with negative weights</li></ul>
|
||
<pre><code class="lang-python">@dataclass
|
||
class BellmanFordResult:
|
||
"""Results from Bellman-Ford algorithm"""
|
||
distances: Dict[int, float]
|
||
parents: Dict[int, Optional[int]]
|
||
has_negative_cycle: bool
|
||
|
||
def get_path(self, target: int) -> Optional[List[int]]:
|
||
"""Reconstruct path if no negative cycle"""
|
||
if self.has_negative_cycle:
|
||
return None
|
||
|
||
if target not in self.parents:
|
||
return None
|
||
|
||
path = []
|
||
current = target
|
||
|
||
while current is not None:
|
||
path.append(current)
|
||
current = self.parents[current]
|
||
|
||
return list(reversed(path))
|
||
|
||
def bellman_ford(graph: 'WeightedGraph', source: int) -> BellmanFordResult:
|
||
"""
|
||
Bellman-Ford shortest path algorithm
|
||
|
||
Handles negative edge weights and detects negative cycles
|
||
"""
|
||
# Initialize
|
||
distances = {v: math.inf for v in range(graph.num_vertices)}
|
||
distances[source] = 0
|
||
parents = {source: None}
|
||
|
||
# Relax all edges V-1 times
|
||
for _ in range(graph.num_vertices - 1):
|
||
for u in range(graph.num_vertices):
|
||
if distances[u] == math.inf:
|
||
continue
|
||
|
||
for edge in graph.adj[u]:
|
||
v = edge.dest
|
||
new_dist = distances[u] + edge.weight
|
||
|
||
if new_dist < distances[v]:
|
||
distances[v] = new_dist
|
||
parents[v] = u
|
||
|
||
# Check for negative cycles
|
||
has_negative_cycle = False
|
||
|
||
for u in range(graph.num_vertices):
|
||
if distances[u] == math.inf:
|
||
continue
|
||
|
||
for edge in graph.adj[u]:
|
||
v = edge.dest
|
||
if distances[u] + edge.weight < distances[v]:
|
||
has_negative_cycle = True
|
||
break
|
||
|
||
if has_negative_cycle:
|
||
break
|
||
|
||
return BellmanFordResult(distances, parents, has_negative_cycle)
|
||
|
||
# Example with negative weights
|
||
graph_neg = WeightedGraph(4, directed=True)
|
||
graph_neg.add_edge(0, 1, 1)
|
||
graph_neg.add_edge(1, 2, -2)
|
||
graph_neg.add_edge(2, 3, 3)
|
||
graph_neg.add_edge(0, 3, 5)
|
||
|
||
result = bellman_ford(graph_neg, source=0)
|
||
print(f"Has negative cycle: {result.has_negative_cycle}") # False
|
||
print(f"Distance to 3: {result.distances[3]}") # 2.0</code></pre>
|
||
<p><strong>SPFA (Shortest Path Faster Algorithm)</strong>:</p>
|
||
<pre><code class="lang-python">from collections import deque
|
||
|
||
def spfa(graph: 'WeightedGraph', source: int) -> BellmanFordResult:
|
||
"""
|
||
SPFA: Queue-based optimization of Bellman-Ford
|
||
|
||
Average case: O(E), worst case: O(V × E)
|
||
Often faster in practice than standard Bellman-Ford
|
||
"""
|
||
distances = {v: math.inf for v in range(graph.num_vertices)}
|
||
distances[source] = 0
|
||
parents = {source: None}
|
||
|
||
queue = deque([source])
|
||
in_queue = {source}
|
||
relax_count = {v: 0 for v in range(graph.num_vertices)}
|
||
|
||
while queue:
|
||
u = queue.popleft()
|
||
in_queue.discard(u)
|
||
|
||
for edge in graph.adj[u]:
|
||
v = edge.dest
|
||
new_dist = distances[u] + edge.weight
|
||
|
||
if new_dist < distances[v]:
|
||
distances[v] = new_dist
|
||
parents[v] = u
|
||
|
||
if v not in in_queue:
|
||
queue.append(v)
|
||
in_queue.add(v)
|
||
|
||
relax_count[v] += 1
|
||
|
||
# Negative cycle detection
|
||
if relax_count[v] >= graph.num_vertices:
|
||
return BellmanFordResult({}, {}, True)
|
||
|
||
return BellmanFordResult(distances, parents, False)</code></pre>
|
||
<h3>3. Floyd-Warshall Algorithm</h3>
|
||
<p><strong>Concept</strong>: Dynamic programming for all-pairs shortest paths</p>
|
||
<p><strong>Properties</strong>:</p>
|
||
<ul><li><strong>Time</strong>: O(V³)</li><li><strong>Space</strong>: O(V²) for distance matrix</li><li><strong>Constraint</strong>: Can detect negative cycles</li><li><strong>Finds</strong>: Shortest paths between all pairs of vertices</li></ul>
|
||
<pre><code class="lang-python">def floyd_warshall(graph: 'WeightedGraph') -> Tuple[List[List[float]],
|
||
List[List[Optional[int]]]]:
|
||
"""
|
||
Floyd-Warshall all-pairs shortest paths
|
||
|
||
Returns:
|
||
(dist, next) where:
|
||
- dist[i][j] = shortest distance from i to j
|
||
- next[i][j] = next vertex on shortest path from i to j
|
||
"""
|
||
n = graph.num_vertices
|
||
|
||
# Initialize distance matrix
|
||
dist = [[math.inf] * n for _ in range(n)]
|
||
next_vertex = [[None] * n for _ in range(n)]
|
||
|
||
# Distance from vertex to itself is 0
|
||
for i in range(n):
|
||
dist[i][i] = 0
|
||
|
||
# Initialize with direct edges
|
||
for u in range(n):
|
||
for edge in graph.adj[u]:
|
||
v = edge.dest
|
||
dist[u][v] = edge.weight
|
||
next_vertex[u][v] = v
|
||
|
||
# Floyd-Warshall: Try each intermediate vertex k
|
||
for k in range(n):
|
||
for i in range(n):
|
||
for j in range(n):
|
||
new_dist = dist[i][k] + dist[k][j]
|
||
|
||
if new_dist < dist[i][j]:
|
||
dist[i][j] = new_dist
|
||
next_vertex[i][j] = next_vertex[i][k]
|
||
|
||
# Check for negative cycles
|
||
for i in range(n):
|
||
if dist[i][i] < 0:
|
||
raise ValueError("Graph contains negative cycle")
|
||
|
||
return dist, next_vertex
|
||
|
||
def reconstruct_path_fw(next_vertex: List[List[Optional[int]]],
|
||
u: int, v: int) -> Optional[List[int]]:
|
||
"""Reconstruct path from u to v using Floyd-Warshall next pointers"""
|
||
if next_vertex[u][v] is None:
|
||
return None
|
||
|
||
path = [u]
|
||
current = u
|
||
|
||
while current != v:
|
||
current = next_vertex[current][v]
|
||
path.append(current)
|
||
|
||
return path
|
||
|
||
# Example usage
|
||
graph = WeightedGraph(4, directed=True)
|
||
graph.add_edge(0, 1, 3)
|
||
graph.add_edge(0, 2, 8)
|
||
graph.add_edge(1, 3, 1)
|
||
graph.add_edge(2, 1, 4)
|
||
graph.add_edge(3, 0, 2)
|
||
graph.add_edge(3, 2, -5)
|
||
|
||
dist, next_v = floyd_warshall(graph)
|
||
path = reconstruct_path_fw(next_v, 0, 2)
|
||
print(f"Shortest path 0→2: {path}") # [0, 1, 3, 2]
|
||
print(f"Distance: {dist[0][2]}") # -1.0</code></pre>
|
||
<h3>4. A* Algorithm</h3>
|
||
<p><strong>Concept</strong>: Informed search using heuristic to guide exploration</p>
|
||
<p><strong>Properties</strong>:</p>
|
||
<ul><li><strong>Time</strong>: Depends on heuristic quality, often much better than Dijkstra</li><li><strong>Space</strong>: O(V) for open/closed sets</li><li><strong>Constraint</strong>: Requires admissible heuristic (never overestimates)</li><li><strong>Finds</strong>: Optimal path if heuristic is consistent</li></ul>
|
||
<pre><code class="lang-python">from typing import Callable
|
||
|
||
def a_star(graph: 'WeightedGraph',
|
||
source: int,
|
||
target: int,
|
||
heuristic: Callable[[int, int], float]) -> Tuple[float, List[int]]:
|
||
"""
|
||
A* shortest path algorithm with heuristic
|
||
|
||
Args:
|
||
graph: Weighted graph
|
||
source: Start vertex
|
||
target: Goal vertex
|
||
heuristic: h(v, target) estimates distance from v to target
|
||
|
||
Returns:
|
||
(distance, path) from source to target
|
||
|
||
Heuristic must be admissible: h(v, target) ≤ true distance
|
||
"""
|
||
# g[v] = cost from source to v
|
||
g_score = {v: math.inf for v in range(graph.num_vertices)}
|
||
g_score[source] = 0
|
||
|
||
# f[v] = g[v] + h(v, target) = estimated total cost
|
||
f_score = {source: heuristic(source, target)}
|
||
|
||
parents = {source: None}
|
||
|
||
# Priority queue: (f_score, vertex)
|
||
open_set = [(f_score[source], source)]
|
||
closed_set = set()
|
||
|
||
while open_set:
|
||
_, current = heapq.heappop(open_set)
|
||
|
||
# Found target
|
||
if current == target:
|
||
path = []
|
||
node = current
|
||
while node is not None:
|
||
path.append(node)
|
||
node = parents[node]
|
||
return g_score[target], list(reversed(path))
|
||
|
||
if current in closed_set:
|
||
continue
|
||
|
||
closed_set.add(current)
|
||
|
||
# Explore neighbors
|
||
for edge in graph.adj[current]:
|
||
neighbor = edge.dest
|
||
|
||
if neighbor in closed_set:
|
||
continue
|
||
|
||
tentative_g = g_score[current] + edge.weight
|
||
|
||
if tentative_g < g_score[neighbor]:
|
||
parents[neighbor] = current
|
||
g_score[neighbor] = tentative_g
|
||
f_score[neighbor] = tentative_g + heuristic(neighbor, target)
|
||
|
||
heapq.heappush(open_set, (f_score[neighbor], neighbor))
|
||
|
||
return math.inf, [] # No path found
|
||
|
||
# Example: Grid graph with Manhattan distance heuristic
|
||
class GridGraph:
|
||
"""2D grid represented as graph"""
|
||
|
||
def __init__(self, width: int, height: int):
|
||
self.width = width
|
||
self.height = height
|
||
self.graph = WeightedGraph(width * height, directed=False)
|
||
|
||
# Connect adjacent cells
|
||
for y in range(height):
|
||
for x in range(width):
|
||
u = y * width + x
|
||
|
||
# Right neighbor
|
||
if x + 1 < width:
|
||
v = y * width + (x + 1)
|
||
self.graph.add_edge(u, v, 1)
|
||
|
||
# Down neighbor
|
||
if y + 1 < height:
|
||
v = (y + 1) * width + x
|
||
self.graph.add_edge(u, v, 1)
|
||
|
||
def manhattan_heuristic(self, v: int, target: int) -> float:
|
||
"""Manhattan distance on grid"""
|
||
v_x, v_y = v % self.width, v // self.width
|
||
t_x, t_y = target % self.width, target // self.width
|
||
return abs(v_x - t_x) + abs(v_y - t_y)
|
||
|
||
# Find path in 10×10 grid
|
||
grid = GridGraph(10, 10)
|
||
source = 0 # Top-left
|
||
target = 99 # Bottom-right
|
||
|
||
dist, path = a_star(
|
||
grid.graph,
|
||
source,
|
||
target,
|
||
lambda v, t: grid.manhattan_heuristic(v, t)
|
||
)
|
||
|
||
print(f"A* path length: {len(path)}") # 19 (Manhattan distance = 18 + 1)
|
||
print(f"Distance: {dist}") # 18.0</code></pre>
|
||
<hr>
|
||
<h2>Patterns</h2>
|
||
<h3>Pattern 1: Algorithm Selection</h3>
|
||
<pre><code class="lang-python">def choose_shortest_path_algorithm(graph_info: dict) -> str:
|
||
"""
|
||
Select optimal shortest path algorithm based on graph properties
|
||
"""
|
||
has_negative_weights = graph_info.get("has_negative_weights", False)
|
||
all_pairs = graph_info.get("all_pairs_needed", False)
|
||
has_heuristic = graph_info.get("has_heuristic", False)
|
||
num_vertices = graph_info["num_vertices"]
|
||
num_edges = graph_info["num_edges"]
|
||
|
||
if all_pairs:
|
||
if num_vertices <= 400:
|
||
return "Floyd-Warshall" # O(V³) acceptable
|
||
else:
|
||
return "Multiple Dijkstra" # V × O(E log V)
|
||
|
||
if has_negative_weights:
|
||
if num_edges < num_vertices * 10:
|
||
return "SPFA" # Often faster for sparse graphs
|
||
else:
|
||
return "Bellman-Ford"
|
||
|
||
if has_heuristic:
|
||
return "A*" # Best for single-target with good heuristic
|
||
|
||
return "Dijkstra" # Default for non-negative weights</code></pre>
|
||
<h3>Pattern 2: Path Reconstruction Helper</h3>
|
||
<pre><code class="lang-python">class ShortestPathSolver:
|
||
"""Unified interface for shortest path algorithms"""
|
||
|
||
@staticmethod
|
||
def solve(graph: 'WeightedGraph',
|
||
source: int,
|
||
target: Optional[int] = None,
|
||
algorithm: str = "auto") -> Dict:
|
||
"""
|
||
Solve shortest path problem with automatic algorithm selection
|
||
"""
|
||
has_negative = any(
|
||
edge.weight < 0
|
||
for u in range(graph.num_vertices)
|
||
for edge in graph.adj[u]
|
||
)
|
||
|
||
if algorithm == "auto":
|
||
if has_negative:
|
||
algorithm = "bellman-ford"
|
||
elif target is not None:
|
||
algorithm = "dijkstra-single"
|
||
else:
|
||
algorithm = "dijkstra"
|
||
|
||
if algorithm == "dijkstra":
|
||
result = dijkstra(graph, source)
|
||
return {
|
||
"algorithm": "Dijkstra",
|
||
"distances": result.distances,
|
||
"get_path": result.get_path
|
||
}
|
||
|
||
elif algorithm == "dijkstra-single":
|
||
dist, path = dijkstra_single_target(graph, source, target)
|
||
return {
|
||
"algorithm": "Dijkstra (single-target)",
|
||
"distance": dist,
|
||
"path": path
|
||
}
|
||
|
||
elif algorithm == "bellman-ford":
|
||
result = bellman_ford(graph, source)
|
||
return {
|
||
"algorithm": "Bellman-Ford",
|
||
"distances": result.distances,
|
||
"has_negative_cycle": result.has_negative_cycle,
|
||
"get_path": result.get_path
|
||
}
|
||
|
||
else:
|
||
raise ValueError(f"Unknown algorithm: {algorithm}")</code></pre>
|
||
<hr>
|
||
<h2>Quick Reference</h2>
|
||
<h3>Algorithm Comparison</h3>
|
||
<p>| Algorithm | Time | Space | Negative Weights | All Pairs | Best Use Case | |-----------|------|-------|------------------|-----------|---------------| | Dijkstra | O((V+E) log V) | O(V) | ❌ | ❌ | Non-negative, single-source | | Bellman-Ford | O(VE) | O(V) | ✅ | ❌ | Negative weights, cycle detection | | SPFA | O(E) avg | O(V) | ✅ | ❌ | Sparse graphs, negative weights | | Floyd-Warshall | O(V³) | O(V²) | ✅ | ✅ | Small graphs, all pairs | | A* | Heuristic-dependent | O(V) | ❌ | ❌ | Single target with heuristic |</p>
|
||
<h3>When to Use Which</h3>
|
||
<ul><li><strong>Dijkstra</strong>: Default for non-negative weights, best performance</li><li><strong>Bellman-Ford</strong>: Negative weights, need cycle detection</li><li><strong>SPFA</strong>: Optimization of Bellman-Ford for sparse graphs</li><li><strong>Floyd-Warshall</strong>: All-pairs distances, small graphs (V ≤ 400)</li><li><strong>A</strong>*: Single target, good heuristic available (games, robotics)</li></ul>
|
||
<hr>
|
||
<h2>Anti-Patterns</h2>
|
||
<h3>❌ Using Dijkstra with Negative Weights</h3>
|
||
<pre><code class="lang-python"># WRONG: Dijkstra fails with negative weights
|
||
graph.add_edge(0, 1, -5)
|
||
result = dijkstra(graph, 0) # Incorrect results!
|
||
|
||
# CORRECT: Use Bellman-Ford or SPFA
|
||
result = bellman_ford(graph, 0)</code></pre>
|
||
<h3>❌ Not Checking for Negative Cycles</h3>
|
||
<pre><code class="lang-python"># WRONG: Assume result is valid
|
||
result = bellman_ford(graph, 0)
|
||
print(result.distances[target]) # May be incorrect!
|
||
|
||
# CORRECT: Check for negative cycle
|
||
result = bellman_ford(graph, 0)
|
||
if result.has_negative_cycle:
|
||
print("No shortest path exists (negative cycle)")
|
||
else:
|
||
print(result.distances[target])</code></pre>
|
||
<h3>❌ Using Floyd-Warshall for Large Graphs</h3>
|
||
<pre><code class="lang-python"># WRONG: O(V³) for 10,000 vertices = 10¹² operations
|
||
large_graph = WeightedGraph(10000)
|
||
dist, next_v = floyd_warshall(large_graph) # Too slow!
|
||
|
||
# CORRECT: Run Dijkstra from each vertex
|
||
for source in range(large_graph.num_vertices):
|
||
result = dijkstra(large_graph, source)
|
||
# Process result</code></pre>
|
||
<hr>
|
||
<h2>Related Skills</h2>
|
||
<p><strong>Next Steps</strong>:</p>
|
||
<ul><li><code>minimum-spanning-tree.md</code> → Kruskal and Prim algorithms</li><li><code>network-flow-algorithms.md</code> → Max flow, min cost flow</li><li><code>graph-applications.md</code> → Real-world routing and navigation</li></ul>
|
||
<p><strong>Foundations</strong>:</p>
|
||
<ul><li><code>graph-theory-fundamentals.md</code> → Basic graph concepts</li><li><code>graph-data-structures.md</code> → Efficient graph representations</li><li><code>graph-traversal-algorithms.md</code> → BFS and DFS basics</li></ul>
|
||
<hr>
|
||
<h2>Summary</h2>
|
||
<p>Shortest path algorithms find optimal routes in weighted graphs:</p>
|
||
<ul><li><strong>Dijkstra</strong>: Greedy algorithm for non-negative weights, O((V+E) log V)</li><li><strong>Bellman-Ford</strong>: DP for negative weights with cycle detection, O(VE)</li><li><strong>Floyd-Warshall</strong>: DP for all-pairs shortest paths, O(V³)</li><li><strong>A</strong>*: Informed search with heuristic guidance</li></ul>
|
||
<p><strong>Key takeaways</strong>:</p>
|
||
<ol><li>Dijkstra is fastest for non-negative weights</li><li>Bellman-Ford handles negative weights and detects negative cycles</li><li>Floyd-Warshall computes all-pairs distances but scales O(V³)</li><li>A* outperforms Dijkstra when good heuristic is available</li><li>Always validate graph properties before algorithm selection</li></ol>
|
||
<p><strong>Next</strong>: Move to <code>minimum-spanning-tree.md</code> for MST algorithms.</p>
|
||
<footer>
|
||
<div class="fmap">
|
||
<div><b>Build</b>
|
||
<a href="https://hanzo.app">hanzo.app</a> app builder
|
||
<a href="https://hanzo.codes">hanzo.codes</a> code with an agent
|
||
<a href="https://hanzoskills.com">hanzoskills.com</a> what an agent reads</div>
|
||
<div><b>Run</b>
|
||
<a href="https://console.hanzo.ai">console.hanzo.ai</a> cloud console
|
||
<a href="https://api.hanzo.ai">api.hanzo.ai</a> the API</div>
|
||
<div><b>Account</b>
|
||
<a href="https://hanzo.id">hanzo.id</a> sign in
|
||
<a href="https://pay.hanzo.ai">pay.hanzo.ai</a> top up
|
||
<a href="https://billing.hanzo.ai">billing.hanzo.ai</a> invoices and usage</div>
|
||
<div><b>Company</b>
|
||
<a href="https://hanzo.ai">hanzo.ai</a> canonical
|
||
<a href="https://hanzo.ventures">hanzo.ventures</a> ventures</div>
|
||
</div>
|
||
<div class="fend"><a href="/shortest-path-algorithms.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
|
||
</footer>
|
||
</div></body></html> |