首页 > 代码库 > Dijkstra、Dij + heap、Floyd、SPFA、 SPFA + SLF Template
Dijkstra、Dij + heap、Floyd、SPFA、 SPFA + SLF Template
Dijkstra in Adjacency matrix :
int Dijkstra(int src,int tec, int n){ bool done[1005]; int d[1005]; memset(done,0,sizeof(done)); map[0][src] = 0;//巧妙之处，加入超级源点0 for(int i = 0;i <= n;i++) d[i] = (i == src ? 0 : 1000000); for(int i = 0;i <= n;i++){//最多执行n+1次操作 int minx,minn = 1000000; for(int j = 0;j <= n;j++)//先找到d[]最小的点 if(!done[j] && d[j] < minn){ minn = d[j]; minx = j; } done[minx] = 1;//将该点加入集合 if(minx == ter) return d[minx]; for(int j = 0;j <= n;j++){//再更新所有的d[] if(!done[j] && d[minx] + map[minx][j] < d[j]){ d[j] = d[minx] + map[minx][j]; } } } return -1;//如果没有找到到终点的路径，返回-1 }
Dijkstra in Adjacency list :
int dijkstra(int src,int ter){//src源点,ter终点 vist[src] = 1; dist[src] = 0; for(int i = head[src];i != -1;i = edge[i].pre ){ dist[edge[i].cur] = edge[i].w; //dist[x]保存从源点到节点x当前最短距离 } for(int i = 1;i < n;i ++){ int cur = 0,Min = inf; for(int j = 1;j <= n;j ++){ if(!vist[j] && dist[j] < Min){ Min = dist[j]; cur = j; } } vist[cur] = 1; if(cur == ter) return dist[cur]; //当ter被标记为访问过时，说明当前dist[ter]已经为src到ter的最短距离 for(int j = head[cur];j != -1;j = edge[j].pre ){ int to = edge[j].cur; if(!vist[to]){ dist[to] = min(dist[to],dist[cur] + edge[j].w); } } } return dist[ter]; }
Dijkstra + heap :
int dijkstra(int src,int ter){ vist[src] = 1; dist[src] = 0; priority_queue<node>q; /* struct node{ int v,dist;//顶点和距离 node(int vv,int ddist){v=vv,dist=ddist;} bool operator<(const node &A)const{return dist > A.dist;}//最小优先 }; */ q.push(node(src,0)); int cur = src; for(int i = 0;i < n;i ++){ for(int j = head[cur];j != -1;j = edge[j].pre ){ int to = edge[j].cur; if(!vist[to] && dist[to]>dist[cur]+edge[j].w){ dist[to] = dist[cur] + edge[j].w; q.push(node(to,dist[to])); } } while(!q.empty()&&vist[q.top().v]){ q.pop(); } cur = q.top().v;q.pop(); vist[cur] = 1; if(cur == ter)break; } return dist[ter]; }
Floyd ：
简单描述一下Floyd：首先我们需要一个邻接矩阵
（所谓邻接矩阵是一个 n*n 的矩阵, 第i行第j列的值为value 表示i点到j点的距离为value
.若i到j点不可达时我们可以使value=http://www.mamicode.com/inf）
注意传递闭包的概念, 得到一个传递闭包至多将任意两点松弛n次。
第一层for是用k点去松弛, 第二层和第三层for是对于任意两点i、j。
#define inf 1000000000 // init*************** for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) dp[i][j] = inf; //**************** //--------------Floyd: for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++)if(i!=k && dp[i][k] != inf) for(int j = 1; j <= n; j++)if(j!=i && j!=k) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]); //-------------- for(int i = 1; i <= n; i++) dp[i][i] = 0;
SPFA：
1、注意对于最短路中存在负权判定：对于spfa算法
当某个点入队列（入队列的意义就是该点被松弛了(更新)）次数>n次，
就说明该点在负权上（可以简单证明一个点至多被更新n次(n为图中的顶点数)）。
2、优先队列：出队的元素不是在队尾的元素，
而是队列中最小的元素（我们有时可以在队列中存储结构体元素，只需重载运算符即可）。
| 1 2 3 4 5 | struct node{ int x, y; bool operator<(const node&a) const { if(a.x==x) return a.y<y; return a.x<x; } //根据x,y值比较node结构体的大小}; |
3、状态压缩：当某些状态只有true or false,时我们可以用一个整数来表示这个状态。
示例：
有3块不同的蛋糕编号1、2、3, 被老鼠啃过, 那么蛋糕只有2种状态, 我们用0表示没有被啃过, 1表示被啃过。
显然我们可以得到所有状态：000、001、010、011、100、101、110、111.
而上述二进制数对应的整数为 [0, 2^3) . （如二进制011 = 整数3表示 第2、3块蛋糕被啃过，第一块蛋糕没有被啃过）
我们可以用 for(int i = 0; i < (1<<3); i++) 来遍历所有的状态。
把多个事物的状态利用二进制含义压缩为一个整数称为状态压缩。
4、利用优先队列优化最短路时, 我们可以先出队距离起点最近的点, 则若出队的为终点显然我们已经得到了一条最短路了。
SPFA in Adjacency list :
int spfa(){ //for(int i=src;i<=ter;i++) dis[i]=-INF; queue<int>q; q.push(src); vis[src]=1; dis[src]=0; while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u]; i!=-1; i=Edge[i].next){ int v=Edge[i].v; if(dis[v]<dis[u]+Edge[i].val){ dis[v]=dis[u]+Edge[i].val; if(!vis[v]){ vis[v]=1; q.push(v); } } } } return dis[ter]; }
SPFA + SLF in Adjacency list :
int spfa(int src,int ter){ //for(int i=src;i<=ter;i++) dis[i]=-INF; deque<int>q; q.push_back(src); vis[src] = 1;//标记当前顶点是否在队列中 dis[src] = 0; while(!q.empty()){ int u = q.front(); q.pop_front(); vis[u] = 0; for(int i = head[u];i != -1;i = Edge[i].next){ int v = Edge[i].v; if(dis[v] < dis[u] + Edge[i].val){//松弛 dis[v] = dis[u] + Edge[i].val; if(!vis[v]){ vis[v] = 1; if(!q.empty()&&dis[v]<dis[q.front()])//SLF优化 q.push_front(v); else q.push_back(v); } } } } return dis[ter]; }