(1)Dijkstra 算法
1. 算法时间复杂度: O(N2)
2. 算法特点:
该算法是用来计算从一个点到其他所有点的最短路径算法, 也是一种单源最短路径算法该算法不能处理存在负边权的情况
3. 算法描述
起点: s dis[v]:s 到 v 的最短路径 pre[v]:v 的前驱节点
初始化: dis[v]=(vs) dis[s]=0 pre[s]=0
- for (int i = 1; i <= n; i++) {
- // 在没有被访问过的点中找一个顶点 u 使得 dis[u] 最小
- //u 标记为已确定的最短路径
- // 找与 u 相连的每一个未确定的最短路径的顶点 v
- if (dis[u] + w[u][v] < dis[v]) {
- dis[v] = dis[u] + w[u][v];
- pre[v] = u;
- }
- }
(2)SPFA 算法
1. 算法时间复杂度: O(kE)E = 边数, K = 常数, 平均值 = 2
2.something
SPFA 是 Bellman-Ford 算法的一种队列实现, 减少了不必要的一些计算可以说是 Bellman-Ford + 队列优化形式上与 BFS 极其相似的一种单元最短路径算法
但是在 BFS 中, 只要有个点出队列, 就不可能再一次进队列了但是 SPFA 不同在 SPFA 中, 一个点在出队列之后有可能又被放入了队列
3. 算法实现
dis[i]: 从起点 s 到 i 的最短路径 w[i][j]: 链接 i 和 j 的边长度 pre[v]: 前趋
team[n]: 队列 and head = 头指针, tail = 尾指针
初始化: dis[s]=0,dis[v]=(vs), 将 exist 数组用 memset 函数全部赋为 false
- // 起点入队
- do {
- // 头指针下移 1 位, 取出指向的点 u
- exist[u] = false
- //for 与 u 相连的所有点 v (不要枚举所有点, 如果那样好像就成了 BMF 了 (好像不是这样啊最起码要慢不少))
- if (dis[v] > dis[u] + w[u][v]) {
- dis[v] = dis[u] + w[u][v];
- pre[v] = u;
- if (!exist[v]) {
- // 尾指针下移 1 位, v 入队列
- exist[v] = true;
- }
- }
- } while ( head < tail );
下面是杂谈:
这几天在信竞老师那里学最短路径算法老师说最后学弗洛伊德 BMF 算法由于有 SPFA 的存在, 就不再说了
这几天在学校的 OJand 洛谷上写最短路径和一些图论题和一些水题
等过一段时间我上了弗洛伊德算法后在继续完成剩余的部分吧
3 月 25 号就市赛了, 争取进市队自己预计了一下, 大概有 35% 的可能性吧
在这里, 还祝要省选的大佬们加油 (怎么扯到这上面来了)!
来源: http://www.bubuko.com/infodetail-2490288.html