图论基础算法
NO.1 Floyd（多源最短路） 数据结构：邻接矩阵 特点：数据规模不能大（<1000）复杂度O(n^3) 五行代码：
//Floyd void floyd(){ for(int k=0;k<n;k++){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ dp[i][j]=min(dp[i][j],(dp[i][k]+dp[k][j])); } } } } //传递闭包问题的修改版 void floyd(){ for(int k=0;k<n;k++){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ dp[i][j]=dp[i][j]||(dp[i][k]&&dp[k][j]); } } } }NO.2 dijkstra 数据结构：邻接表 特点：单源最短路问题 无法处理负环 代码如下：
const int MAXINT = 32767; const int MAXNUM = 10; int dist[MAXNUM]; int prev[MAXNUM]; int A[MAXUNM][MAXNUM]; void Dijkstra(int v0) { bool S[MAXNUM]; // 判断是否已存入该点到S集合中 int n=MAXNUM; for(int i=1; i<=n; ++i) { dist[i] = A[v0][i]; S[i] = false; // 初始都未用过该点 if(dist[i] == MAXINT) prev[i] = -1; else prev[i] = v0; } dist[v0] = 0; S[v0] = true; for(int i=2; i<=n; i++) { int mindist = MAXINT; int u = v0; // 找出当前未使用的点j的dist[j]最小值 for(int j=1; j<=n; ++j) if((!S[j]) && dist[j]<mindist) { u = j; // u保存当前邻接点中距离最小的点的号码 mindist = dist[j]; } S[u] = true; for(int j=1; j<=n; j++) if((!S[j]) && A[u][j]<MAXINT) { if(dist[u] + A[u][j] < dist[j]) //在通过新加入的u点路径找到离v0点更短的路径 { dist[j] = dist[u] + A[u][j]; //更新dist prev[j] = u; //记录前驱顶点 } } } }如果带有优先级，可用优先队列优化。
NO.3 SPFA 楼上的改进版，优化对负环的处理 代码如下：
//bfs 万能啊 int spfa_bfs(int s) { queue <int> q; memset(d,0x3f,sizeof(d)); d[s]=0; memset(c,0,sizeof(c)); memset(vis,0,sizeof(vis)); q.push(s); vis[s]=1; c[s]=1; //顶点入队vis要做标记，另外要统计顶点的入队次数 int OK=1; while(!q.empty()) { int x; x=q.front(); q.pop(); vis[x]=0; //队头元素出队，并且消除标记 for(int k=f[x]; k!=0; k=nnext[k]) //遍历顶点x的邻接表 { int y=v[k]; if( d[x]+w[k] < d[y]) { d[y]=d[x]+w[k]; //松弛 if(!vis[y]) //顶点y不在队内 { vis[y]=1; //标记 c[y]++; //统计次数 q.push(y); //入队 if(c[y]>NN) //超过入队次数上限，说明有负环 return OK=0; } } } } return OK; } //dfs处理负环更快，但是仅限于有限深度 int spfa_dfs(int u) { vis[u]=1; for(int k=f[u]; k!=0; k=e[k].next) { int v=e[k].v,w=e[k].w; if( d[u]+w < d[v] ) { d[v]=d[u]+w; if(!vis[v]) { if(spfa_dfs(v)) return 1; } else return 1; } } vis[u]=0; return 0; }Page 1 2017-04-13 Orion JNU
