在图论和理论计算机科学中，最长路径问题是指在给定的图中找出长度最长的简单路径。一条不具有任何重复顶点的路径被称为简单路径。无权图中路径的长度就是边的数量，而有权图中路径长度是边权重之和。不同的是，与此相反的最短路径问题（不含负权环）可以在多项式时间内解决。而最长路径问题是NP困难的，这意味着除非P =...

最大或最小的子集。闭包问题可以看作最大流问题的简化版，在多项式时间内被解决。实际上，是否有环对于找到闭包没有影响。 基于拓扑排序的性质，有向无环图的最短路问题和最长路径问题可以在线性时间内解决。将顶点拓扑排序后，从前到后遍历每一个顶点，对于遍历到的顶点，更新其所有出边所到达顶点的长度值。如果求最...

图论中的经典问题哈密顿路径问题（台湾作漢米頓路徑問題）（Hamiltonian path problem）与哈密顿环问题（台湾作漢米頓環問題）（Hamiltonian cycle problem）分别是来确定在一个给定的图上是否存在哈密顿路径（一条经过图上每个顶点的路径）和哈密顿环（一条经过图上每个顶点的环）。两个问题皆为NP完全。...

深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如无权最长路径问题等等。 因发明“深度优先搜索算法”，約翰·霍普克洛夫特与罗伯特·塔扬在1986年共同获得计算机领域的最高奖：图灵奖。 首先将根节点放入stack中。...

克斯特拉算法使用类似廣度优先搜索的方法解决赋权图的单源最短路径问题。 该算法存在很多变体：戴克斯特拉的原始版本仅适用于找到两个顶点之间的最短路径，后来更常见的变体固定了一个顶点作为源结点然后找到该顶点到图中所有其它结点的最短路径，产生一个最短路径树。 该算法解决了圖 G = ⟨ V , E ⟩ {\displaystyle...

purchaser problem）与车辆路径问题的一种特殊情况。 作为计算复杂性理论中一个典型的判定性问题，TSP的一个版本是给定一个图和长度 L，要求回答图中是否存在比 L 短的回路（英语：circuit或tour）。该问题被划分为NP完全问题。已知TSP算法最...

附带依赖安装时间顺序的单机总延迟问题（SMTTPDST） 附带顺序相依设置/转换时间的多阶段流水车间调度问题（MFSP） 限量车辆路径问题（CVRP） 多站车辆路径问题（MDVRP） 周期车辆路径问题（PVRP） 分批配送车辆路径问题（SDVRP） 随机车辆路径问题（SVRP） 装货配送的车辆路径问题（VRPPD）...

将所有盘子移动到另一个柱子的最短路径只有一个。 对于任意的两个盘子分布情况之间转换的时候， 只有一个或者两个不同的最短路径。 对于任意的盘子分布情况， 都有一个或者两个将所有盘子移动到任意一个柱子上的最长不相交路径。 对于任意的两个盘子分布情况之间转换的时候， 只有一个或者两个不同的最长不相交路径。 设 N h...

Floyd-Warshall算法（英語：Floyd-Warshall algorithm），中文亦称弗洛伊德算法或佛洛依德算法，是解决任意两点间的最短路径的一种算法，可以正確處理有向圖或负权（但不可存在负权回路）的最短路径問題，同时也被用于计算有向图的传递闭包。 Floyd-Warshall算法的时间复杂度為 O ( | V | 3 )...

贝尔曼-福特算法（英語：Bellman–Ford algorithm），求解单源最短路径问题的一种算法，由理查德·貝尔曼和小萊斯特·倫道夫·福特创立。有时候这种算法也被称为貝爾曼-福特-摩爾算法（Bellman–Ford–Moore algorithm），因为愛德華·F·摩爾也为这个算法的发展做出了贡献。它的原理是对图进行...

中国邮递员问题（也称路线检查问题，Route Inspection Problem）是一个图论问题。此問題為在一個連通的無向圖中找到一最短的封閉路徑，且此路徑需通過所有邊至少一次。现实意义中，中国邮递员问题就是在一個已知的地區，郵差要設法找到一條最短路徑，走過此地區所有的街道，且最後要回到出發點。 此問題...

要知道为什么这些性质确保了这个结果，注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。 在很多树数据结构的表示中，一个节点有可能只有一个子节点，而叶子节...

当一个问题显示出最优子结构ーー意味着一个问题的最优解可以从子问题的最优解构造出来ーー和重叠子问题，意味着同一个子问题可以用来解决许多不同的问题实例时，一种叫做动态规划的快速方法可以避免重新计算已经计算出来的解。例如，Floyd-Warshall 算法，在一个加权图中，通过使用从所有相邻顶点到达目标的最短路径...

路径名访问文件的API在没有支持驱动程序的情况下无法看到新的、更长的名称。 由于FAT长文件名的实现是建立在一个更老的、更有限的命名系统之上的，因此不可避免地会有一些复杂的问题，例如當试图创建太多的前六个字母相同的文件。 而且，在根目录中创建文件或文件夹比在其他目錄更可能遇上問題...

{\displaystyle n+1} 条外部路径，它们分别表示数组元素之间以及数组边界之外的各个区间。 同样地，这一问题可以简化为确定含 n {\displaystyle n} 个节点的所有二叉树中的最小外部路径长度。对于任意二叉树，外部路径长度与内部路径长度之间满足 E ( n ) = I ( n...

d}  被定义为最大的偏心率： d = max v ∈ V ϵ ( v ) {\displaystyle d=\max _{v\in V}\epsilon (v)} ，也即最远的两点间的距离。若要求得一张图的直径，首先要求得任意两点之间的最短路径，在这些所有的最短路径中，取其长度最长者，即是这张图的直径。...

开放式最短路径优先（英語：Open Shortest Path First，缩写为 OSPF）是广泛使用的一种路由协议，它属于链路状态路由协议，具有路由变化收敛速度快、无路由环路、支持变长子网掩码（VLSM）和汇总、层次区域划分等优点。 OSPF是一种基于IP协议的路由协议。它是大中型网络上使用较为...

在数学中，线积分（英語：Line integral）是积分的一种。积分函数的取值沿的不是区间，而是被称为积分路径的特定曲线。 在曲线积分中，被积的函数可以是标量函数或向量函数。當被積函數是純量函數時，积分的值是積分路径各点上的函数值乘上該點切向量的長度，在被积分函数是向量函数时，積分值是積分向量函数与曲线切向量...

問題，除此之外，方法像是正交分頻多工、犁耙接收器也可被使用。 在全球定位系統接收器中，多重路徑效應會使靜止的接收器的輸出顯示隨機跳動。雖然在物體移動時此現象可能會變得不明顯，但仍然會因為這樣而降低定位的精確度和速度估測。 聲音的多重路徑為最簡單的例子。假設原本聲音為 x...

等微觀物體的波動性與粒子性的實驗。雙縫實驗是一種「雙路徑實驗」。在雙路徑實驗裏，微觀物體可以同時通過兩條路徑或通過其中任意一條路徑，從初始點抵達最終點。這兩條路徑的程差促使描述微觀物體物理行為的量子態發生相移，因此產生干涉現象。另一種常見的雙路徑實驗是马赫-曾德尔干涉仪實驗。...

程。这个过程有各种各样的处理规则，包括统一转换为小写、移除“.”和“..”片段，以及在非空路径里插入斜杆。 有些爬虫希望从指定的网站中尽可能地爬取资源。而路径上移爬虫就是为了能爬取每个URL里提示出的每个路径。 例如，给定一个Http的种子URL: http://llama.org/hamster/monkey/page...

algorithm）是一种动态规划算法。它用于寻找最有可能产生观测事件序列的维特比路径——隐含状态序列，特别是在马尔可夫信息源上下文和隐马尔可夫模型中。 术语“维特比路径”和“维特比算法”也被用于寻找观察结果最有可能解释相关的动态规划算法。例如在统计句法分析中动态规划算法可以被用于发现最可能的上下文无关的派生（解析）的字符串，有时被称为“维特比分析”。...

principle）最早由法国科学家皮埃爾·德·費馬在1662年提出：光传播的路径是光程取极值的路径。这个极值可能是极大值、极小值或函数的拐点。 最初提出时，又名「最短時間原理」：光線傳播的路徑是需時最少的路徑。 費馬原理更正確的稱謂應是「平穩時間原理」：光沿着所需时间为平稳的路径...

{\displaystyle G} 是k-边连通的最大整数。 计算机科学中最有名的问题之一。 一笔画问题、也看哈密尔顿环。 库拉托夫斯基定理描述了有点平面图。有名的欧拉公式也说：V-E+F=2. 这是欧拉示性数。 路径（walk），又译作途径。一个长度为 k {\displaystyle k} 的路径是一个非空的顶点和边的交错序列...

导出子图的重要类型包括如下内容： 导出路径是路径的子图。无权图中任意两个顶点之间的最短路径是一个导出路径，因为任意一对顶点之间的附加边，如果可能导致它不能被导出也会导致它不是最短。反之，在距离遗传图中，所有导出路径都是最短路径。 导出周期是诱导子图或循环。图的围长由其最...

路徑的入射角等於反射角。稍後，亞歷山卓的希羅證明這路徑的長度是最短的。 1662年，皮埃爾·德·費馬提出費馬原理，又稱為「最短時間原理」：光線移動的路徑是需時最少的路徑。 費馬原理更正確的版本應是「平穩時間原理」。對於某些狀況，光線移動的路徑所需的時間可能不是最小值，而是最...

太陽路徑是指由於地球環繞太陽的軌道造成太陽季節性的每小時位置變化 (和日照長度)。太陽的相對位置是影響建築物的太陽能系統獲得熱增益的性能最主要因素。精確的知道太陽路徑和氣候條件是經濟的設置太陽能集熱器區域、定位、庭園設計、夏季遮陰、和太陽追蹤器等，不可或缺的專門知識。 要有效的收集太陽能，太陽能收集器...

所有信号能够准时到达，并保证电路的正常功能。 静态时序分析可以检查电路中各条路径诸如毛刺、延迟路径和时钟偏移等问题。 关键路径被定义为从输入端到达输出端所经历的最大延迟路径。一旦电路时序通过下面所述的方法进行计算，关键路径可以很容易地通过追溯的方法被找到。 到达时间是指信号到达电路指定位置所需要经...

最短时间是从开始点到完成点的最长路径的长度（路径上各活动持续时间之和）。路径长度最长的路径叫做关键路径。假设开始点是 v 1 {\displaystyle v_{1}} ，从 v 1 {\displaystyle v_{1}} 到 v i {\displaystyle v_{i}} 的最长路径长度叫做事件...

徑，對應到同樣兩個面相連的展開圖中，也能找到這條路徑。最短路徑的其他可能結果也包括了穿過與這兩個面共同相鄰的第三面的路徑，哪條才是最短路徑可以看該路徑在合適的展開圖上是否為直線，並比較其距離來決定。 蜘蛛和蒼蠅問題是一個在長方體上兩點之間找到最短路徑的娛樂數學謎題。...

{\displaystyle O(B^{M})} ，其中B是最大分支係數，而M是樹的最長路徑長度。由於對空間的大量需求，因此BFS並不適合解非常大的問題，對於類似的問題，應用IDDFS以達節省空間的效果。 最差情形下，BFS必須尋找所有到可能節點的所有路徑，因此其時間複雜度為 O ( | V | + | E...