Dijkstra.算法的分析（正确性） o本质是一个greedy?算法： 口每一步找当前的最优解，不会调整已经得到的结果 口但是一般情况下locali最优并不一定是globali最优 巧的是Dijkstra.算法就是global:最优 口只需证明第i步将u:标记为已知时，一定是s到u的global:最优解 算法第步找出的最短路径 能否存在s到v 更近的路径？ 已知点的集合S 不能。因为存在就意味着有不 在S中的点w。此时，s到w的距 Source s 离一定小于s到v的距离，矛盾
本质是一个greedy算法： 每一步找当前的最优解，不会调整已经得到的结果 但是一般情况下local最优并不一定是global最优 巧的是Dijkstra算法就是global最优 只需证明第i步将ui标记为已知时，一定是s到ui的global最优解 Dijkstra算法的分析（正确性） 已知点的集合S v 算法第i步找出的最短路径 w 能否存在s到v 更近的路径？ Source s dv dw 不能。因为存在就意味着有不 在S中的点w。此时，s到w的距 离一定小于s到v的距离，矛盾
本节提要 ▣内容1：Dijkstra算法 口内容2：Floyd-Warshall:算法 ▣内容3：旅行商问题(TSP) ▣内容4：最大流问题
内容1：Dijkstra算法 内容2：Floyd-Warshall算法 内容3：旅行商问题（TSP） 内容4：最大流问题* 本节提要
求所有结点间的最短距离？ Dijkstras算法 口不能处理负边 O(V E Ig V)with binary heap 一OIVI3IgIV)if dense ☐Floyd-Warshall算法 口可以处理负边，只要没有负的回路 口O(IVI),无需fancy的数据结构 口动态规划算法：存储并利用子问题的解
求所有结点间的最短距离？ Dijkstra算法 不能处理负边 O(|V| |E| lg |V|) with binary heap — O(|V|3 lg |V|) if dense Floyd-Warshall 算法 可以处理负边，只要没有负的回路 O(|V|3 ) ，无需fancy的数据结构 动态规划算法：存储并利用子问题的解