Shortest-Path

释义 Definition

最短路径：在一张图（或道路网络）中，从起点到终点总成本最小的一条路径；“成本”通常指距离、时间、权重之和等。在计算机科学中常指图论/算法里的“Shortest Path Problem”（最短路问题）。

发音 Pronunciation (IPA)

/ˌʃɔːrtɪst ˈpæθ/

例句 Examples

The app always chooses the shortest path to your destination.
这个应用总是选择到达目的地的最短路径。

To deliver packages efficiently, the company models streets as a weighted graph and computes the shortest path for each driver.
为了高效配送，这家公司把街道建模为加权图，并为每位司机计算最短路径。

词源 Etymology

由 shortest（“最短的”，short 的最高级）+ path（“路径/小路”）构成的组合词。随着交通规划与计算机图论的发展，“shortest path”逐渐固定为一个术语，用来指代在给定规则（距离、时间、权重）下的最优路线。

相关词 Related Words

• Algorithm
• Dijkstra
• Graph
• Route
• Optimization
• Breadth-First Search
• Weighted
• Edge
• Vertex

文学与作品 Literary Works

• Thomas H. Cormen et al. Introduction to Algorithms（常称 CLRS）：以“shortest paths”作为经典章节主题之一。
• Edsger W. Dijkstra “A note on two problems in connexion with graphs”（1959）：提出著名的最短路径算法（Dijkstra 算法）。
• Robert Sedgewick & Kevin Wayne Algorithms：在图算法部分系统讲解最短路径相关问题与实现。
• Donald E. Knuth The Art of Computer Programming：在算法与图相关讨论中涉及最短路径等典型问题。