单源最短路径贪心算法贪在哪

单源最短路径贪心算法通常指的是Dijkstra算法或其变种，如Floyd-Warshall算法。这些算法的核心思想都是在每一步选择当前未找到最短路径的节点中，贪心地选取距离源点最近的一个节点进行扩展。

- **Dijkstra算法**：从源点开始，每次都选择当前距离源点最短的节点，并更新与其相邻节点的距离。这个过程不断迭代，直到找到所有节点的最短路径或确定不存在更短路径为止。

- **Floyd-Warshall算法**：适用于所有节点对之间的最短路径查找，不是单源的。它使用动态规划的思想，每次迭代都考虑所有节点对之间的中间节点，贪心地更新可能的最短路径。

贪心之处在于，这些算法在局部最优决策（即每次选择当前看起来最优的决策）的基础上，希望达到全局最优解。然而，它们并不能保证一定能找到全局最优路径，比如在存在负权边的情况下，Dijkstra算法可能无法给出正确的结果。