路径（图论）
lù jìng (tú lùn)
图中的路径是由边连接、且不重复经过任何顶点的一列顶点,表示穿过图的一条路线。
Definition
图中的路径是从一个顶点到另一个顶点、沿边前进且不重复经过任何顶点的一条路线，是一条不折返到已经去过的地方的踪迹。严格地说，路径是一列互不相同的顶点 $v_0, v_1, \ldots, v_k$，使得每一对相邻的顶点 $\{v_i, v_{i+1}\}$ 都是一条边；路径的长度是 $k$，一条闭合路径（$v_0 = v_k$）是一个圈，如果任意两个顶点之间都存在路径，图就是连通的。距离 $d(u,v)$ 是从 $u$ 到 $v$ 的最短路径的长度；$G$ 的直径是 $\max_{u,v} d(u,v)$，围长是最短圈的长度，最短路径可由迪杰斯特拉算法（权重非负）或贝尔曼-福特算法（允许负权重，能检测负圈）求出。
Example
在城市地图图中，从家到学校的一条路径可能是家、图书馆、公园、学校，每个地方恰好经过一次。在一个顶点为 $\{1,2,3,4\}$、边为 $\{12,23,34,14\}$ 的图中，路径 $1$-$2$-$3$-$4$ 的长度为 $3$，并且是哈密顿路径（经过每个顶点恰好一次）。P 与 NP 问题在这里联系密切：寻找哈密顿路径是 NP 完全问题，而寻找欧拉路径（遍历每条边一次）可以在多项式时间内解决，寻找最短路径属于 P 类问题，这一二分法说明约束条件的细微变化能极大地改变算法的难度。
Key Insight
寻找两个顶点之间的最短路径是图论中最重要的问题之一，可由迪杰斯特拉算法和贝尔曼-福特算法这类算法解决。在代数图论中，从 $u$ 到 $v$、长度为 $k$ 的通路数目等于邻接矩阵的 $k$ 次幂 $A^k$ 中 $(u,v)$ 位置的元素，把路径计数与线性代数联系了起来。