最短路径算法

定义

最短路径算法用于寻找图中两个节点之间的权重和最小的路径，根据图的类型（有无负权重、单源/多源）选择不同算法。

常见算法

算法 适用场景 时间复杂度 支持负权重
Dijkstra 单源、非负权重 O((V+E)logV) ❌
Bellman-Ford 单源、可含负权重 O(VE) ✅
A* 单源、有启发函数 取决于启发函数 ❌
Floyd 多源 O(V³) ✅

相关概念

Link to this note

图

type: concept tags:图数据结构图论 created: 2026-05-04 updated: 2026-05-04图 (Graph)定义图是由若干**节点（Vertex）和边（Edge）**构成的数据结构，是对复杂网络关系的抽象。图可以看作是多叉树结构的延伸——多叉树只允许父节点指向子节点，而图中节点之间可以相互指向，形成更复杂的网络结构。基本组成| 组成 | 说明 | |------|------| | 节点 (Vertex) | 图的基本组成单元，每个节点有唯一标识 | | 边 (Edge) | 连接两个节点的线，可以是有向或无向 |常见类型按方向分类有向图 (Directed Graph)：边有方向，只能沿箭头方向到达无向图 (Undirected Graph)：边无方向，可双向到达按权重分类加权图 (Weighted Graph)：边带权重，可表示距离、成本等无权图 (Unweighted Graph)：边无权重按密度分类稠密图 (Dense Graph)：$E$ 接近 $V^2$，几乎每两个节点间都有边稀疏图 (Sparse Graph)：$E$ 远小于 $V^2$，边很少存储方式1. 邻接表 (Adjacency List)每个节点存储一个列表，记录与其相连的所有节点适合稀疏图，空间复杂度 $O(V+E)$2. 邻接矩阵

index

Harness Engineering Wiki - 内容索引本页面由 Claude 自动维护，每次 ingest 新资料后更新📊 Stats总页面数: 151实体页: 2概念页: 81摘要页: 62对比页: 6最后更新: 2026-05-09📚 摘要页 (Summaries)| 页面链接

图结构的通用代码实现-总结

type: summary tags: [图结构, 数据结构, 算法, 邻接表, 邻接矩阵] source: "[[raw/articles/2026/05/图结构的通用代码实现-原文]]" created: 2026-05-04 updated: 2026-05-04图结构的通用代码实现⚠️ 注意：由于原文使用 JavaScript 动态渲染，本文档仅包含提取到的部分内容（开头约 22 行）。完整内容请访问原文：图结构的通用代码实现核心观点[[图]]是多叉树结构的延伸。两者的主要区别：树结构：只允许父节点指向子节点，子节点之间不会互相链接图结构：节点之间可以相互指向，形成复杂的网络结构基本概念图结构逻辑上由两部分构成：节点（Vertex）：图中的顶点边（Edge）：连接节点的线常见存储方式邻接表（Adjacency List）邻接矩阵（Adjacency Matrix）图 vs 多叉树| 特性 | 多叉树 | 图 | |------|--------|-----| | 指向关系 | 父 → 子（单向） | 节点间可相互指向 | | 循环 | 不允许 | 允许 | | 复杂度

Interactive Graph