找到节点之间的最短路径是一个基本的图问题。这项能力在许多机器学习 (machine learning)场景中很必要，例如分析社交网络中的影响力传播、优化物流路线、找出图中表示的实体间的语义相似度，甚至理解复杂生物网络中的连接。
最短路径问题的定义
“最短路径”取决于我们如何定义“短”。
- 图： 在边没有设定权重 (weight)或成本的图中，最短路径就是边数最少的路径。正如我们在讨论图遍历时所看到的，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。
迪杰斯特拉算法
对于找出所有边权重 (weight)为非负的加权图中的最短路径，迪杰斯特拉算法是一种基础方法。它能找出从单一源节点到图中所有其他节点的最短路径。
迪杰斯特拉算法的核心思想是维护一组已访问节点（这些节点到源节点的最短路径已知）和到未访问节点的暂时距离。它迭代地选择具有最小暂时距离的未访问节点，将其标记 (token)为已访问，并更新其未访问邻居的暂时距离。此过程很大程度上依赖于优先队列（通常使用堆实现，如第 5 章所述）来有效获取具有最小距离的未访问节点。
算法步骤（高层次）：
- 初始化：
- 将源节点的暂时距离设为 0，将所有其他节点设为无限大。
- 将所有节点标记为未访问。
- 使用所有节点初始化优先队列，按其暂时距离排序。
- 迭代： 当优先队列不为空时：
- 从优先队列中提取具有最小暂时距离的节点
u。将 u 标记为已访问。
- 对于
u 的每个未访问邻居 v：
- 计算从源到
v 经过 u 的距离：distance(source, u) + weight(u, v)。
- 如果此计算距离小于
v 当前的暂时距离，则更新 v 的距离并可能更新其在优先队列中的位置。
- 终止： 当优先队列为空，或者当目标节点（如果寻找到达特定目标的路径）已被访问时，算法终止。记录的距离即为从源节点出发的最短路径距离。
性能： 借助高效的优先队列实现（例如二叉堆），迪杰斯特拉算法通常在 O(E+VlogV) 时间内运行，其中 V 是顶点数量，E 是边数量。
限制： 迪杰斯特拉算法仅在边权重为非负时才保证最优性。如果图中包含负边权重，它可能产生不正确的结果，因为通过负边重新访问节点可能导致比之前找到的更短的路径，这违反了算法的假设。
其他算法
尽管迪杰斯特拉算法是基础的，但其他算法处理最短路径问题的不同变体：
- 贝尔曼-福特算法： 此算法可以处理具有负边权重 (weight)的图。它通过反复松弛边来工作，最多松弛 V−1 次。如果在 V−1 次迭代后距离仍能改进，则表明存在从源节点可达的负权重环。其时间复杂度为 O(VE)，对于稠密图来说比迪杰斯特拉算法慢，但在存在负权重时是必要的。
- A* 搜索算法： A* 是一种启发式搜索算法，常用于特定起点和终点之间的路径寻找。它通过使用启发式函数 h(n) 来增强迪杰斯特拉算法，该函数估算从节点 n 到目标的成本。它根据 f(n)=g(n)+h(n) 对节点进行排序，其中 g(n) 是从源节点到节点 n 的已知成本。如果启发函数是可接受的（从不高估实际成本），A* 能找出最优路径。其效率很大程度上取决于启发函数的质量。
- 弗洛伊德-沃沙尔算法： 如果需要找出图中所有节点对之间的最短路径，弗洛伊德-沃沙尔算法是常用选择。它使用动态规划迭代地考虑潜在路径的中间节点。其时间复杂度为 O(V3)，这使其适用于需要所有节点对信息的小型或稠密图。
在机器学习 (machine learning)中的关联
最短路径算法不仅仅是理论工具；它们在机器学习中有实际用途：
- 特征工程： 图中两个节点（例如社交网络中的用户、语义网络中的词语）之间最短路径的长度或成本，可以是预测模型的有力特征。
- 网络分析： 了解中心性、影响力或信息流通常涉及分析数据图表示中的路径长度。
- 推荐系统： 在二分图中或通过中间连接寻找用户与项目之间的路径，可以为相似度度量和推荐逻辑提供依据。
- 图嵌入 (embedding)： 尽管在推断期间不直接计算最短路径，但一些图嵌入技术在学习节点的向量 (vector)表示时，会隐含地捕捉路径信息。
理解图中最短路径找出背后的原理，尤其是在加权场景中使用迪杰斯特拉等算法，能使您更有效地分析关系数据并在机器学习流程中运用图结构。了解不同算法之间的权衡，使您能够根据图的特性（加权/非加权、是否存在负边）和特定问题要求（单源、所有节点对）选择合适的工具。
