找到节点之间的最短路径是一个基本的图问题。这项能力在许多机器学习场景中很必要,例如分析社交网络中的影响力传播、优化物流路线、找出图中表示的实体间的语义相似度,甚至理解复杂生物网络中的连接。最短路径问题的定义“最短路径”取决于我们如何定义“短”。图: 在边没有设定权重或成本的图中,最短路径就是边数最少的路径。正如我们在讨论图遍历时所看到的,BFS 自然地能按边数计算,找出从源节点到所有其他可达节点的最短路径。这是因为 BFS 逐层遍历图,确保首次到达一个节点时,是通过边数最少的路径。"* 加权图: 场景通常涉及与遍历边相关的成本、距离或概率。在这些加权图中,两个节点之间的最短路径是指路径上边的权重总和最小的路径。找出这条路径需要比 BFS 更高级的算法。"让我们考虑一个简单的加权图:graph G { layout=neato; node [shape=circle, style=filled, fillcolor="#a5d8ff", fontname="Helvetica", fontsize=10]; edge [fontname="Helvetica", fontsize=9, color="#868e96"]; A [pos="0,1.5!"]; B [pos="1.5,1.5!"]; C [pos="0,0!"]; D [pos="1.5,0!"]; E [pos="3,0.75!"]; A -- B [label=" 4 "]; A -- C [label=" 2 "]; B -- E [label=" 3 "]; C -- D [label=" 1 "]; D -- E [label=" 5 "]; C -- B [label=" 1 "]; // 额外添加以供参考 }一个简单的加权无向图。边上的数字代表权重或成本。在上图中,从 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 章所述)来有效获取具有最小距离的未访问节点。算法步骤(高层次):初始化:将源节点的暂时距离设为 0,将所有其他节点设为无限大。将所有节点标记为未访问。使用所有节点初始化优先队列,按其暂时距离排序。迭代: 当优先队列不为空时:从优先队列中提取具有最小暂时距离的节点 u。将 u 标记为已访问。对于 u 的每个未访问邻居 v:计算从源到 v 经过 u 的距离:distance(source, u) + weight(u, v)。如果此计算距离小于 v 当前的暂时距离,则更新 v 的距离并可能更新其在优先队列中的位置。终止: 当优先队列为空,或者当目标节点(如果寻找到达特定目标的路径)已被访问时,算法终止。记录的距离即为从源节点出发的最短路径距离。性能: 借助高效的优先队列实现(例如二叉堆),迪杰斯特拉算法通常在 $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)$,这使其适用于需要所有节点对信息的小型或稠密图。在机器学习中的关联最短路径算法不仅仅是理论工具;它们在机器学习中有实际用途:特征工程: 图中两个节点(例如社交网络中的用户、语义网络中的词语)之间最短路径的长度或成本,可以是预测模型的有力特征。网络分析: 了解中心性、影响力或信息流通常涉及分析数据图表示中的路径长度。推荐系统: 在二分图中或通过中间连接寻找用户与项目之间的路径,可以为相似度度量和推荐逻辑提供依据。图嵌入: 尽管在推断期间不直接计算最短路径,但一些图嵌入技术在学习节点的向量表示时,会隐含地捕捉路径信息。理解图中最短路径找出背后的原理,尤其是在加权场景中使用迪杰斯特拉等算法,能使您更有效地分析关系数据并在机器学习流程中运用图结构。了解不同算法之间的权衡,使您能够根据图的特性(加权/非加权、是否存在负边)和特定问题要求(单源、所有节点对)选择合适的工具。