常见最短路径算法概览

  1. Dijkstra算法 🔍
    适用于带权重的有向图，寻找单源最短路径。使用优先队列优化时间复杂度为 $O(E + V \log V)$。

    最短路径_Dijkstra
    [点击查看Dijkstra算法实现示例](/coding_practice/leetcode/graph_theory/shortest_path_examples)

  2. Bellman-Ford算法 ⏱️
    可处理负权边，时间复杂度为 $O(VE)$。适合检测图中是否存在负权环。

    最短路径_Bellman_Ford

  3. Floyd-Warshall算法 🌐
    计算所有顶点对之间的最短路径，时间复杂度 $O(V^3)$。适合稠密图场景。

    最短路径_Floyd_Warshall
    [深入理解Floyd-Warshall算法](/coding_practice/leetcode/graph_theory/shortest_path_analysis)

练习建议

  • 从Dijkstra算法题目开始实践
  • 尝试用不同语言实现算法（如Python/Java/C++）
  • 注意处理图的表示方式（邻接矩阵 vs 邻接表）
  • 每日挑战：用O(VlogV)复杂度解决单源最短路径问题

扩展知识

📘 图论基础概念是理解最短路径算法的前提
🧠 算法优化技巧：使用堆结构加速Dijkstra算法，或尝试SPFA算法（队列优化的Bellman-Ford）