单源最短路

{ for (int k = 1; k <= n; ++k)

for (int i = 1; i <= n; ++i)

for (int j = 1; j <= n; ++j)

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

}

Floyd本质上是一个动态规划的思想，每一次循环更新经过前k个节点，i到j的最短路径。

实际的思想就是，每次都考虑之前的最短路径，以及经过k节点，能否使得i→k +k→j的路径和小于i→j的路径。

初始化dist数组时，用int_max，i→i的路径填0。

算法本质就是暴搜，但是能搜出来就不错了

单源最短路

Bellman-Ford算法:

需要一个一维数组dist[]来存储每个点到起点的距离，设起点为S，终点为D，那这条最短路一定是S->P1->P2->...- >D的形式。

思想和上面的算法非常一致，就是暴力破解。

你想求出某点到其他所有点的最短路径：

第一次遍历，你求得了与固定点一步可达的点的结果，其余点的结果未知

第二次遍历，就得到了你求得了与固定点两步可达的点的结果。

依次类推，只要图中不存在环，你遍历节点个数-2次，一定会得到所有的最短路径结果。这里用的是链式前向星存图

void Bellman_Ford(int n, int m)

{ for (int j = 0; j < n - 1; ++j)

for (int i = 1; i <= m; ++i)

dist[edges[i].to] = min(dist[edges[i].to], dist[edges[i].from] + edges[i].w);

}

SPFA算法:

观察发现，Bellman-Ford算法第一次遍历时，可能更新的点只可能是S能直接到达的点。

然后下一次可能被更新的则是S能直接到达的点能直接到达的点。

SPFA算法正是利用了这种思想，并进行了优化。

借用队列这一数据结构，在每次对点操作时更新它能到达的点，并把队列中不存在的点加入队列，并出队操作结束

如果一个点已经在队列里，便不重复入队

如果一条边未被更新，那么它的终点不入队

void SPFA(int s)//s为固定点编号，inqueue数组判断节点是否在队列中 {

queue<int> Q;

Q.push(s);

while (!Q.empty())

{ int p = Q.front();

Q.pop();

inqueue[p] = 0;

for (int e = head[p]; e != 0; e = edges[e].next)

{ int to = edges[e].to;

if (dist[to] > dist[p] + edges[e].w)

{ dist[to] = dist[p] + edges[e].w;

if (!inqueue[to])

{ inqueue[to] = 1;

Q.push(to);

} }

} }

}

然而它的时间复杂度不稳定，和上一种算法的思路是相同的，因此在最坏情况下，时间复杂度为O(mn)

Dijkstra算法：

Dij基于一种贪心的思想，我们假定有一张没有负边的图，首先，起点到起点的距离为0，对起点和它能直接到达的所有点进行更新。

因为没有负边，遍历起点直连的节点，更新达到的节点的dist，这时可以肯定，离起点最近的那个顶点的dist一定已经是最终结果，不可能有比它更小的结果了。

这时候找到了起点直达的最短路径的点，以这个点为开始，对它能到达的点进行更新，此时就确定了可以从起点和起点直达的最短路径的点开始的最短路径值，每次更新后都选剩下为确定点中dist最小的节点去更新，直到所有节

点都确定下来。

如何取出离给定点最近的点？优先级队列。

在一个点被访问前，优先队列里会存储这个点被更新的整个历史，出队时是按照从路径从小到大的顺序出队，由于小路径的时候已经此节点出队并判断过了，因此大的路径出队时直接跳过这个节点的处理即可。