什么是路径：对比通路、轨迹与路径 | 集智百科

“集智百科精选”是一个长期专栏，持续为大家推送复杂性科学相关的基本概念和资源信息。作为集智俱乐部的开源科学项目，集智百科希望打造复杂性科学领域最全面的百科全书，欢迎对复杂性科学感兴趣、热爱知识整理和分享的朋友加入！

本文是对集智百科中“路径”词条的摘录，参考资料及相关词条请参阅百科词条原文。

本词条由集智俱乐部众包生产，难免存在纰漏和问题，欢迎大家留言反馈或者前往对应的百科词条页面进行修改，一经修改，可以获得对应的积分奖励噢！

本词条由集智俱乐部众包生产，难免存在纰漏和问题，欢迎大家留言反馈或者前往对应的百科词条页面进行修改，一经修改，可以获得对应的积分奖励噢！

目录

一、定义二、例子三、路径寻找
四、编者推荐五、集智百科词条志愿者招募

在图论 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。

• 如果两条路径没有任何共同的内部顶点，那么它们与顶点无关（换言之，内部顶点不相交）。类似地，如果两条路径没有任何共同的内边，那么它们是边独立的（或边不相交）。两条内部顶点不相交的路径的边也不相交，但反之未必正确的。

• 图中两个顶点之间，如果最短路径存在，那么它们的的距离是最短路径的长度，否则该距离是无穷大。

• 连接图的直径是图的顶点对之间的最大距离（如上定义）。

路径寻找

求解图的最短和最长路径有多种算法，但是前者的计算比后者简单得多。

Dijkstra 算法产生了一个从源顶点到无向或有向图中每个顶点的最短路径列表，而Bellman-Ford 算法 可以应用于具有负边权重的有向图。利用 Floyd-Warshall 算法可以求出加权有向图中所有顶点对之间的最短路径。

编者推荐

网络动力学课程

集智学园特邀陈关荣、项林英、樊瑛、宣琦、李翔、史定华、李聪、荣智海、周进、王琳等网络科学专家作为导师，依托汪小帆、李翔、陈关荣的经典教材《网络科学导论》，自2月27日起开展系列上线课程，以网络动力学为主线构建网络科学知识体系。欢迎希望进入网络科学领域、提高网络分析能力、与一线专家探讨问题的朋友报名参加！

点击查看课程详情：

课程推荐：网络科学导论 | 网络科学集智课堂第二期 

https://campus.swarma.org/course/2328

百科项目志愿者招募

作为集智百科项目团队的成员，本文内容由Ryan，CecileLi，薄荷参与贡献。我们也为每位作者和志愿者准备了专属简介和个人集智百科主页，更多信息可以访问其集智百科个人主页。

以上内容都是我们做这项目的起点，作为来自不同学科和领域的志愿者，我们建立起一个有效的百科团队，分配有审校、翻译、编辑、宣传等工作。我们秉持：知识从我而来，问题到我为止的信念，认真负责编撰每一个词条。

在这里从复杂性知识出发与伙伴同行，同时我们希望有更多志愿者加入这个团队，使百科词条内容得到扩充，并为每位志愿者提供相应奖励与资源，建立个人主页与贡献记录，使其能够继续探索复杂世界。

如果你有意参与更加系统精细的分工，扫描二维码填写报名表，我们期待你的加入！

集智百科报名表

来源：集智百科

编辑：王建萍

推荐阅读

点击“阅读原文”，阅读路径相关内容与参考文献