最短路径

• Dijkstra算法
  • 单源最短路径算法，用于求一个源点到其他点的最短距离。
  • 算法的本质是贪心，从源点开始，每次从未被访问的顶点中选出一个与源点距离最近的点，然后更新这个点的邻接点的最短距离和前驱结点。
  • 不能处理带负权边的图，原因是对于Dijkstra算法来说，已访问过的点是不会再被更新的，如果某个未访问的点与已访问过的点距离为负，那实际上应该要更新已访问过的点的最短距离，比如下面这个图：
    
    以a为起点，第一次会选出b作为最近的点，更新最短距离为1并设置b为已访问状态，接下来从b的邻接点中选出c，这里虽然可以更新c的最短距离为-1（c->b->a），但并不会更新b到a的最短距离为0（b->c->a）。
• Floyd算法 
  • 任意两点间最短路径算法，本质是动态规范。
  • 先枚举任意的两个点，再枚举剩下的点，看能不能通过剩下的点来更新这两个点的距离，如果可以，则更新最短距离和前驱结点。
  • 可以处理带负权边的图，但不能处理带负权环的图。

以上两种算法都不能处理带负权环的图，因为对于带负权环的图，只要不停地在负权环里兜圈，路径之和就会越来越小。