什么是路径：对比通路、轨迹与路径 | 集智百科
本词条由集智俱乐部众包生产，难免存在纰漏和问题，欢迎大家留言反馈或者前往对应的百科词条页面进行修改，一经修改，可以获得对应的积分奖励噢！
目录
四、编者推荐五、集智百科词条志愿者招募
在图论 Graph theory中，图中的路径 path是一个有限或无限的边序列，这些边连接着一系列顶点，这些顶点在大多数定义中都是不同的(又因为这些顶点是不同的，所以图中的边也是不同的)。有向图中的有向路径 directed path（有时也称为dipath），是一个有限或无限的边序列，它连接一系列不同的顶点，并具有附加一个条件：序列中所有的边都方向都相同。
图1：一个三维的超立方体图表显示一个红色的哈密顿图，和一个黑色的最长诱导路径
路径是图论的基本概念，在大多数图论文本的导论部分都有描述，见Bondy and Murty（1976） ， Gibbons（1985），或Diestel（2005）。Korte（1990）等人著作中，涵盖了更多关于图中路径的高级算法的话题。
定义
通路 轨迹 路径 Walk, trail, path
图2：从A到E的轨迹，非路径
通路 Walk：是连接一系列顶点形成的有限或无限的边序列。 以一个图为例 G = ( V, E, ϕ ) 。有限通路 finite walk是一系列的边 ( e1, e2, …, en − 1 )，其顶点序列( v1, v2, …, vn ) 。 ϕ ( ei ) = {vi, vi + 1}对于i = 1, 2, …, n − 1。( v1, v2, …, vn ) 是移动的顶点序列。如果 v1 = vn ，则此通路封闭，反之则开放。无限通路 infinite walk是由一系列边组成的，它们的类型与这里描述的相同，但没有起点或终点，而一个半无限通路(或光线)则有起点但是没有终点。 轨迹 trail是所有的边缘都清晰可见的通路。 路径 path是一条所有顶点（包括所有边）都是不同的轨迹。
如果 w = ( e1, e2, …, en − 1 )是有顶点的序列 (v1, v2, …, vn)，那么w 就是从 v1 到 vn的有限通路。同样，对于一条轨迹或者一条路径也是如此。如果两个不同的顶点之间有一个有限通路，那么在它们之间也有一条有限的轨迹和一条有限的路径。
有些学者对路径的定义中并不要求它的所有顶点都是不同的，而是使用术语“简单路径”来指代这样的路径。
一个加权图 weighted graph将一个值（权重）与图中的每条边相关联。一个加权图中的通路（或轨迹或路径）的权是所有边的权之和。有时，“成本 cost”或“长度 length”这两个词可以用来指代“权重”这一概念。
有向的通路，轨迹，路径 Directed walk, trail, path
有向通路 directed walk是指由连接一系列顶点的边沿相同方向定向形成的有限或无限序列。
以一个有向图 G = ( V, E, ϕ ) 为例。有限有向通路由一系列的边组成 ( e1, e2, …, en − 1 )，而对于这些边，又存在一系列的顶点 ( v1, v2, …, vn )。 ϕ ( ei ) = ( vi, vi + 1 )对于 i = 1, 2, …, n − 1 。( v1, v2, …, vn )是有向通路的顶点序列。无限有向通路是一个边序列，其类型与本文描述的相同，但起点或终点，而半无限有向通路（或射线）有起点，但没有终点。
有向轨迹 directed trail是指所有边都可见的轨迹。
有向路径 directed path是指所有顶点都不同的有向路径。
假设一个通路 w = ( e1, e2, …, en − 1 )是顶点序列有限的( v1, v2, …, vn )有向通路，那么w就是从 v1 到 vn的通路。同样，对于有向轨迹或路径也是如此。如果在两个不同的顶点之间存在有限有向通路，那么在它们之间也存在有限有向轨迹和有限有向路径。
有些学者并不要求有向路径的所有顶点都是不同的，因此他们用“简单有向路径 simple directed path”这个术语来表示它。
一个加权有向图将一个值（权重）与有向图中的每条边相关联。加权有向图中有向通路（或路径）的权是有向边权重的和。有时，“成本 cost”或“长度 length”这两个词可以用来指代“权重”这一概念。
例子
如果路径包含每一对顶点，那么图就是连通的。
如果一个有向图中存在包含每对顶点的相对有向路径，那么这就是强连接有向图 Strongly-connected digraph。
没有边连接两个不连续的路径顶点的路径称为诱导路径 induced path。
包含图的每个顶点的路径称为哈密顿路径 Hamiltonian Path。
如果两条路径没有任何共同的内部顶点，那么它们与顶点无关（换言之，内部顶点不相交）。类似地，如果两条路径没有任何共同的内边，那么它们是边独立的（或边不相交）。两条内部顶点不相交的路径的边也不相交，但反之未必正确的。
图中两个顶点之间，如果最短路径存在，那么它们的的距离是最短路径的长度，否则该距离是无穷大。
连接图的直径是图的顶点对之间的最大距离（如上定义）。
路径寻找
编者推荐
网络动力学课程
集智学园特邀陈关荣、项林英、樊瑛、宣琦、李翔、史定华、李聪、荣智海、周进、王琳等网络科学专家作为导师，依托汪小帆、李翔、陈关荣的经典教材《网络科学导论》，自2月27日起开展系列上线课程，以网络动力学为主线构建网络科学知识体系。欢迎希望进入网络科学领域、提高网络分析能力、与一线专家探讨问题的朋友报名参加！
课程推荐：网络科学导论 | 网络科学集智课堂第二期 https://campus.swarma.org/course/2328
百科项目志愿者招募
作为集智百科项目团队的成员，本文内容由Ryan，CecileLi，薄荷参与贡献。我们也为每位作者和志愿者准备了专属简介和个人集智百科主页，更多信息可以访问其集智百科个人主页。
在这里从复杂性知识出发与伙伴同行，同时我们希望有更多志愿者加入这个团队，使百科词条内容得到扩充，并为每位志愿者提供相应奖励与资源，建立个人主页与贡献记录，使其能够继续探索复杂世界。
如果你有意参与更加系统精细的分工，扫描二维码填写报名表，我们期待你的加入！
来源：集智百科
编辑：王建萍
点击“阅读原文”，阅读路径相关内容与参考文献