求图中最短路径算法之Floyd-Warshall算法——C++实现

Floyed-Warshall算法使用动态规划的思想来计算图中所有节点对之间的最短路径，其运行时间复杂度为O(V^3)，该算法的约束条件为图中不能包含权值之和为负的环，但可以包含权值为负的边。该算法相对于Dijkstra算法而言较难理解，建议感兴趣的可以阅读《算法导论》这本书中的第25章，里面分析的比较全面。动态规划思想运用范围比较广，对其深刻理解并能灵活运用比较难，所以在学习Floyed-Warshall算法时，为了加深理解，我用C++将其实现。Floyed-Warshall算法使用动态规划的思想来计算图中所有节点对之间的最短路径，其运行