最短路径算法概述

找到节点之间的最短路径是一个基本的图问题。这项能力在许多机器学习场景中很必要，例如分析社交网络中的影响力传播、优化物流路线、找出图中表示的实体间的语义相似度，甚至理解复杂生物网络中的连接。

最短路径问题的定义

“最短路径”取决于我们如何定义“短”。

• 图： 在边没有设定权重或成本的图中，最短路径就是边数最少的路径。正如我们在讨论图遍历时所看到的，BFS 自然地能按边数计算，找出从源节点到所有其他可达节点的最短路径。这是因为 BFS 逐层遍历图，确保首次到达一个节点时，是通过边数最少的路径。

"* 加权图： 场景通常涉及与遍历边相关的成本、距离或概率。在这些加权图中，两个节点之间的最短路径是指路径上边的权重总和最小的路径。找出这条路径需要比 BFS 更高级的算法。"

让我们考虑一个简单的加权图：

一个简单的加权无向图。边上的数字代表权重或成本。

在上图中，从 A 到 E 的最短路径是 A -> C -> B -> E，总权重为 $2 + 1 + 3 = 6$。路径 A -> B -> E 的权重为 $4 + 3 = 7$，路径 A -> C -> D -> E 的权重为 $2 + 1 + 5 = 8$。

迪杰斯特拉算法

对于找出所有边权重为非负的加权图中的最短路径，迪杰斯特拉算法是一种基础方法。它能找出从单一源节点到图中所有其他节点的最短路径。

迪杰斯特拉算法的核心思想是维护一组已访问节点（这些节点到源节点的最短路径已知）和到未访问节点的暂时距离。它迭代地选择具有最小暂时距离的未访问节点，将其标记为已访问，并更新其未访问邻居的暂时距离。此过程很大程度上依赖于优先队列（通常使用堆实现，如第 5 章所述）来有效获取具有最小距离的未访问节点。

算法步骤（高层次）：

1. 初始化：
   • 将源节点的暂时距离设为 0，将所有其他节点设为无限大。
   • 将所有节点标记为未访问。
   • 使用所有节点初始化优先队列，按其暂时距离排序。
2. 迭代： 当优先队列不为空时：
   • 从优先队列中提取具有最小暂时距离的节点 u。将 u 标记为已访问。
   • 对于 u 的每个未访问邻居 v：
     • 计算从源到 v 经过 u 的距离：distance(source, u) + weight(u, v)。
     • 如果此计算距离小于 v 当前的暂时距离，则更新 v 的距离并可能更新其在优先队列中的位置。
3. 终止： 当优先队列为空，或者当目标节点（如果寻找到达特定目标的路径）已被访问时，算法终止。记录的距离即为从源节点出发的最短路径距离。

性能： 借助高效的优先队列实现（例如二叉堆），迪杰斯特拉算法通常在 $O(E + V \log V)$ 时间内运行，其中 $V$ 是顶点数量，$E$ 是边数量。

限制： 迪杰斯特拉算法仅在边权重为非负时才保证最优性。如果图中包含负边权重，它可能产生不正确的结果，因为通过负边重新访问节点可能导致比之前找到的更短的路径，这违反了算法的假设。

其他算法

尽管迪杰斯特拉算法是基础的，但其他算法处理最短路径问题的不同变体：

• 贝尔曼-福特算法： 此算法可以处理具有负边权重的图。它通过反复松弛边来工作，最多松弛 $V-1$ 次。如果在 $V-1$ 次迭代后距离仍能改进，则表明存在从源节点可达的负权重环。其时间复杂度为 $O(VE)$，对于稠密图来说比迪杰斯特拉算法慢，但在存在负权重时是必要的。
• A* 搜索算法： A* 是一种启发式搜索算法，常用于特定起点和终点之间的路径寻找。它通过使用启发式函数 $h(n)$ 来增强迪杰斯特拉算法，该函数估算从节点 $n$ 到目标的成本。它根据 $f(n) = g(n) + h(n)$ 对节点进行排序，其中 $g(n)$ 是从源节点到节点 $n$ 的已知成本。如果启发函数是可接受的（从不高估实际成本），A* 能找出最优路径。其效率很大程度上取决于启发函数的质量。
• 弗洛伊德-沃沙尔算法： 如果需要找出图中所有节点对之间的最短路径，弗洛伊德-沃沙尔算法是常用选择。它使用动态规划迭代地考虑潜在路径的中间节点。其时间复杂度为 $O(V^3)$，这使其适用于需要所有节点对信息的小型或稠密图。

在机器学习中的关联

最短路径算法不仅仅是理论工具；它们在机器学习中有实际用途：

• 特征工程： 图中两个节点（例如社交网络中的用户、语义网络中的词语）之间最短路径的长度或成本，可以是预测模型的有力特征。
• 网络分析： 了解中心性、影响力或信息流通常涉及分析数据图表示中的路径长度。
• 推荐系统： 在二分图中或通过中间连接寻找用户与项目之间的路径，可以为相似度度量和推荐逻辑提供依据。
• 图嵌入： 尽管在推断期间不直接计算最短路径，但一些图嵌入技术在学习节点的向量表示时，会隐含地捕捉路径信息。

理解图中最短路径找出背后的原理，尤其是在加权场景中使用迪杰斯特拉等算法，能使您更有效地分析关系数据并在机器学习流程中运用图结构。了解不同算法之间的权衡，使您能够根据图的特性（加权/非加权、是否存在负边）和特定问题要求（单源、所有节点对）选择合适的工具。