最短路径三件套：BFS、Dijkstra、A* 工程实战 ACERS 解析

A -> B -> D
A -> C -> D

从 A 到 D 的最短边数 = 2
可行路径: A-B-D 或 A-C-D

A -> B (2)
A -> C (5)
B -> C (1)
B -> D (4)
C -> D (1)

A 到 D 最短代价 = 4
路径: A-B-C-D

from collections import deque
import heapq
from math import inf


def reconstruct_path(parent, s, t):
    if t not in parent and s != t:
        return []
    path = [t]
    while path[-1] != s:
        path.append(parent[path[-1]])
    path.reverse()
    return path


def bfs_shortest_path(graph, s, t, max_depth=None):
    """graph[u] = [v1, v2, ...]"""
    q = deque([(s, 0)])
    parent = {s: s}
    visited = {s}

    while q:
        u, d = q.popleft()
        if u == t:
            return d, reconstruct_path(parent, s, t)
        if max_depth is not None and d >= max_depth:
            continue
        for v in graph.get(u, []):
            if v not in visited:
                visited.add(v)
                parent[v] = u
                q.append((v, d + 1))

    return inf, []


def dijkstra_shortest_path(graph, s, t, max_cost=None):
    """graph[u] = [(v, w), ...], w >= 0"""
    dist = {s: 0.0}
    parent = {s: s}
    pq = [(0.0, s)]

    while pq:
        du, u = heapq.heappop(pq)
        if du != dist.get(u, inf):
            continue
        if max_cost is not None and du > max_cost:
            continue
        if u == t:
            return du, reconstruct_path(parent, s, t)
        for v, w in graph.get(u, []):
            nd = du + w
            if nd < dist.get(v, inf):
                dist[v] = nd
                parent[v] = u
                heapq.heappush(pq, (nd, v))

    return inf, []


def astar_shortest_path(graph, s, t, h):
    """h(u) is admissible heuristic estimate from u to t"""
    g = {s: 0.0}
    parent = {s: s}
    pq = [(h(s), s)]  # (f, node)

    while pq:
        f, u = heapq.heappop(pq)
        if u == t:
            return g[u], reconstruct_path(parent, s, t)

        for v, w in graph.get(u, []):
            ng = g[u] + w
            if ng < g.get(v, inf):
                g[v] = ng
                parent[v] = u
                heapq.heappush(pq, (ng + h(v), v))

    return inf, []


if __name__ == "__main__":
    unweighted = {
        "A": ["B", "C"],
        "B": ["D"],
        "C": ["D"],
        "D": [],
    }
    print(bfs_shortest_path(unweighted, "A", "D"))  # (2, ['A', 'B', 'D']) or C path

    weighted = {
        "A": [("B", 2), ("C", 5)],
        "B": [("C", 1), ("D", 4)],
        "C": [("D", 1)],
        "D": [],
    }
    print(dijkstra_shortest_path(weighted, "A", "D"))  # (4.0, ['A', 'B', 'C', 'D'])

    heuristic = {"A": 3, "B": 2, "C": 1, "D": 0}
    print(astar_shortest_path(weighted, "A", "D", lambda x: heuristic[x]))

from collections import deque


def bidirectional_bfs(graph, s, t, max_depth=6):
    if s == t:
        return 0

    qa, qb = deque([s]), deque([t])
    da, db = {s: 0}, {t: 0}

    while qa and qb:
        # expand smaller frontier first
        if len(qa) <= len(qb):
            q, dcur, dother = qa, da, db
        else:
            q, dcur, dother = qb, db, da

        u = q.popleft()
        if dcur[u] >= max_depth:
            continue

        for v in graph.get(u, []):
            if v in dcur:
                continue
            dcur[v] = dcur[u] + 1
            if v in dother:
                return dcur[v] + dother[v]
            q.append(v)

    return -1

package main

import (
	"container/heap"
	"fmt"
)

type Edge struct{ To string; W float64 }

type Item struct{ D float64; U string }
type PQ []Item
func (p PQ) Len() int { return len(p) }
func (p PQ) Less(i, j int) bool { return p[i].D < p[j].D }
func (p PQ) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func (p *PQ) Push(x interface{}) { *p = append(*p, x.(Item)) }
func (p *PQ) Pop() interface{} { old := *p; x := old[len(old)-1]; *p = old[:len(old)-1]; return x }

func dijkstra(g map[string][]Edge, s, t string) float64 {
	const INF = 1e18
	dist := map[string]float64{s: 0}
	pq := &PQ{{0, s}}
	heap.Init(pq)

	for pq.Len() > 0 {
		it := heap.Pop(pq).(Item)
		if it.D != dist[it.U] { continue }
		if it.U == t { return it.D }
		for _, e := range g[it.U] {
			nd := it.D + e.W
			if d, ok := dist[e.To]; !ok || nd < d {
				dist[e.To] = nd
				heap.Push(pq, Item{nd, e.To})
			}
		}
	}
	return INF
}

func main() {
	g := map[string][]Edge{
		"A": {{"B", 2}, {"C", 5}},
		"B": {{"C", 1}, {"D", 4}},
		"C": {{"D", 1}},
	}
	fmt.Println(dijkstra(g, "A", "D")) // 4
}

function astar(graph, s, t, h, maxDepth = 6) {
  const g = new Map([[s, 0]]);
  const pq = [[h(s), 0, s]]; // [f, depth, node]

  while (pq.length) {
    pq.sort((a, b) => a[0] - b[0]);
    const [f, depth, u] = pq.shift();
    if (u === t) return g.get(u);
    if (depth >= maxDepth) continue;

    for (const [v, w] of (graph.get(u) || [])) {
      const ng = g.get(u) + w;
      if (!g.has(v) || ng < g.get(v)) {
        g.set(v, ng);
        pq.push([ng + h(v), depth + 1, v]);
      }
    }
  }
  return Infinity;
}

from collections import deque

def multi_source_bfs(graph, sources):
    q = deque(sources)
    dist = {s: 0 for s in sources}
    while q:
        u = q.popleft()
        for v in graph.get(u, []):
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

# Dijkstra (non-negative weights), adjacency list
import heapq
from math import inf


def dijkstra(graph, s, t):
    dist = {s: 0.0}
    parent = {s: s}
    pq = [(0.0, s)]

    while pq:
        du, u = heapq.heappop(pq)
        if du != dist.get(u, inf):
            continue
        if u == t:
            break
        for v, w in graph.get(u, []):
            nd = du + w
            if nd < dist.get(v, inf):
                dist[v] = nd
                parent[v] = u
                heapq.heappush(pq, (nd, v))

    if t not in dist:
        return inf, []
    path = [t]
    while path[-1] != s:
        path.append(parent[path[-1]])
    path.reverse()
    return dist[t], path

// Dijkstra O(V^2) demo for dense/small graphs (non-negative weights)
#include <stdio.h>
#define N 5
#define INF 1000000000

int main(void) {
    int g[N][N] = {
        {0, 2, 5, 0, 0},
        {0, 0, 1, 4, 0},
        {0, 0, 0, 1, 0},
        {0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0}
    };
    int s = 0, t = 3;
    int dist[N], vis[N] = {0};

    for (int i = 0; i < N; i++) dist[i] = INF;
    dist[s] = 0;

    for (int i = 0; i < N; i++) {
        int u = -1;
        for (int j = 0; j < N; j++)
            if (!vis[j] && (u == -1 || dist[j] < dist[u])) u = j;
        if (u == -1 || dist[u] == INF) break;
        vis[u] = 1;
        for (int v = 0; v < N; v++) {
            if (g[u][v] > 0 && dist[v] > dist[u] + g[u][v])
                dist[v] = dist[u] + g[u][v];
        }
    }

    if (dist[t] >= INF) printf("unreachable\n");
    else printf("dist=%d\n", dist[t]);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

pair<long long, vector<int>> dijkstra(int n, vector<vector<pair<int,int>>>& g, int s, int t) {
    const long long INF = (1LL<<60);
    vector<long long> dist(n, INF);
    vector<int> parent(n, -1);
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;

    dist[s] = 0;
    parent[s] = s;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [du, u] = pq.top(); pq.pop();
        if (du != dist[u]) continue;
        if (u == t) break;
        for (auto [v, w] : g[u]) {
            long long nd = du + w;
            if (nd < dist[v]) {
                dist[v] = nd;
                parent[v] = u;
                pq.push({nd, v});
            }
        }
    }

    if (dist[t] == INF) return {INF, {}};
    vector<int> path;
    for (int x = t; x != s; x = parent[x]) path.push_back(x);
    path.push_back(s);
    reverse(path.begin(), path.end());
    return {dist[t], path};
}

package main

import (
	"container/heap"
	"fmt"
)

type Edge struct{ To int; W int64 }
type Item struct{ D int64; U int }
type PQ []Item
func (p PQ) Len() int { return len(p) }
func (p PQ) Less(i, j int) bool { return p[i].D < p[j].D }
func (p PQ) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func (p *PQ) Push(x interface{}) { *p = append(*p, x.(Item)) }
func (p *PQ) Pop() interface{} { old := *p; x := old[len(old)-1]; *p = old[:len(old)-1]; return x }

func dijkstra(g [][]Edge, s, t int) int64 {
	const INF int64 = 1<<60
	dist := make([]int64, len(g))
	for i := range dist { dist[i] = INF }
	dist[s] = 0

	pq := &PQ{{0, s}}
	heap.Init(pq)

	for pq.Len() > 0 {
		it := heap.Pop(pq).(Item)
		if it.D != dist[it.U] { continue }
		if it.U == t { return it.D }
		for _, e := range g[it.U] {
			nd := it.D + e.W
			if nd < dist[e.To] {
				dist[e.To] = nd
				heap.Push(pq, Item{nd, e.To})
			}
		}
	}
	return INF
}

func main() {
	g := make([][]Edge, 4)
	g[0] = []Edge{{1, 2}, {2, 5}}
	g[1] = []Edge{{2, 1}, {3, 4}}
	g[2] = []Edge{{3, 1}}
	fmt.Println(dijkstra(g, 0, 3)) // 4
}

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn dijkstra(graph: &Vec<Vec<(usize, i64)>>, s: usize, t: usize) -> i64 {
    let inf = i64::MAX / 4;
    let mut dist = vec![inf; graph.len()];
    let mut pq = BinaryHeap::new();

    dist[s] = 0;
    pq.push((Reverse(0_i64), s));

    while let Some((Reverse(du), u)) = pq.pop() {
        if du != dist[u] { continue; }
        if u == t { return du; }
        for &(v, w) in &graph[u] {
            let nd = du + w;
            if nd < dist[v] {
                dist[v] = nd;
                pq.push((Reverse(nd), v));
            }
        }
    }
    inf
}

fn main() {
    let g = vec![
        vec![(1,2),(2,5)],
        vec![(2,1),(3,4)],
        vec![(3,1)],
        vec![]
    ];
    println!("{}", dijkstra(&g, 0, 3)); // 4
}

// BFS shortest hops in unweighted graph
function bfsShortest(graph, s, t) {
  const q = [[s, 0]];
  const seen = new Set([s]);

  while (q.length) {
    const [u, d] = q.shift();
    if (u === t) return d;
    for (const v of (graph.get(u) || [])) {
      if (!seen.has(v)) {
        seen.add(v);
        q.push([v, d + 1]);
      }
    }
  }
  return Infinity;
}

const g = new Map([
  ["A", ["B", "C"]],
  ["B", ["D"]],
  ["C", ["D"]],
  ["D", []],
]);
console.log(bfsShortest(g, "A", "D")); // 2