图论算法

我们把点分为两类，一类是已确定最短路径的点，称为“白点”，另一类是未确定最短路径的点，称为“蓝点”。如果我们要求出一个点的最短路径，就是把这个点由蓝点变为白点。从起点到蓝点的最短路径上的中转点在这个时刻只能是白点。 Dijkstra的算法思想，就是一开始将起点到起点的距离标记为0，而后进行n次循环，每次找出一个到起点距离dis[u]最短的点u，将它从蓝点变为白点。随后枚举所有的蓝点vi，如果以此白点为中转到达蓝点vi的路径dis[u]+w[u][vi]更短的话，这将它作为vi的“更短路径”dis[vi]（此时还不确定是不是vi的最短路径）。 就这样，我们每找到一个白点，就尝试着用它修改其他所有的蓝点。中转点先于终点变成白点，故每一个终点一定能够被它的最后一个中转点所修改，而求得最短路径。 #include<iostream>

#include #include #include using namespace std; int a[101][3]; double c[101]; bool b[101]; double f[101][101]; int n,i,j,k,x,y,m,s,e; double minl; double maxx = 1e30; int main() { cin >> n; for (i = 1; i <= n; i++) cin >> a[i][1] >> a[i][2]; for (i = 1; i <= n; i++) for(j = 1; j <= n; j++) f[i][j] = maxx; //f数组初始化最大值 cin >> m; for (i = 1; i <= m; i++) //预处理x.y间距离f[x][y] { cin >> x >> y; f[x][y] = f[y][x] = sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2)); } cin >> s >> e; for (i = 1; i <= n; i++) c[i] = f[s][i]; memset(b,false,sizeof(b)); //dijkstra 最短路 b[s] = true; c[s] = 0; for (i = 1; i <= n-1; i++) { minl = maxx; k = 0; for (j = 1; j <= n; j++) //查找可以更新的点 if ((! b[j]) && (c[j] < minl)) { minl = c[j]; k = j; } if (k == 0) break; b[k] = true; for (j = 1; j <= n; j++) if (c[k] + f[k][j] < c[j]) c[j] = c[k] + f[k][j]; } printf("%.2lf\n",c[e]); return 0; } Bellman-Ford算法O(NE) 简称Ford（福特）算法，同样是用来计算从一个点到其他所有点的最短路径的算法，也是一种单源最短路径算法。 能够处理存在负边权的情况，但无法处理存在负权回路的情况（下文会有详细说明）。 算法时间复杂度：O(NE)，N是顶点数，E是边数。 算法实现： 设s为起点，dis[v]即为s到v的最短距离，pre[v]为v前驱。w[j]是边j的长度，且j连接u、v。 初始化：dis[s]=0,dis[v]=∞（v≠s），pre[s]=0 For (i = 1; i <= n-1; i++) For (j = 1; j <= E; j++) //注意要枚举所有边，不能枚举点。 if (dis[u]+w[j]<dis[v]) 　 //u、v分别是这条边连接的两个点。 { dis[v] =dis[u] + w[j]; pre[v] = u; } SPFA算法O(kE) SPFA是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。 主要思想是： 初始时将起点加入队列。每次从队列中取出一个元素，并对所有与它相邻的点进行修改，若某个相邻的点修改成功，则将其入队。直到队列为空时算法结束。 这个算法，简单的说就是队列优化的bellman-ford，利用了每个点不会更新次数太多的特点发明的此算法。 SPFA 在形式上和广度优先搜索非常类似，不同的是广度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是说一个点修改过其它的点之后，过了一段时间可能会获得更短的路径，于是再次用来修改其它的点，这样反复进行下去。 算法时间复杂度：O(kE)，E是边数。K是常数，平均值为2。