概要:
Dijkstra 算法
Bellman-Ford 算法
SPFA 算法
Floyd 算法
1,Dijkstra 算法用于解决单源最短路径问题, 严格讲是无负权图的最短路径问题.
邻接矩阵版
- const int maxv=1000;
- const int INF=1000000000;
- int n,G[maxv][maxv];
- int d[maxv]; // 起点到各点的最短路径长度
- bool vis[maxv]={false};
- void Dijkstra(int s){ //s 为起点
- fill(d,d+maxv,INF);
- d[s]=0;
- for(int i=0;i<n;i++){ // 循环 n 次
- int u=-1,MIN=INF; //u 使 d[u] 最小, MIN 存放最小 d[u]
- for(int j=0;j<n;j++){
- if(vis[j]==false && d[j]<MIN){ // 未收录的顶点中到起点距离最小者
- u=j;
- MIN=d[j];
- }
- }
- // 找不到小于 INF 的 d[u], 说明剩下的顶点和起点 s 不连通
- if(u==-1) return;
- vis[u] =true;
- for(int v=0;v<n;v++){
- if( G[u][v]!=INF && vis[v]==false && d[u]+G[u][v] <d[v]){
- d[v]=d[u]+G[u][v];
- }
- }
- }
- }
邻接表版
- struct Node{
- int v,dis; //v 为边的目标顶点, dis 为边权
- };
- vector<Node> Adj[maxv];
- int n,d[maxv];
- bool vis[maxv]={0};
- void Dijkstra(int s){
- fill(d,d+maxv,INF);
- d[s]=0;
- for(int i=0;i<n;i++) {
- int u=-1,MIN=INF;
- for(int j=0;j<n;j++){
- if(d[j]<MIN && vis[j]==false){
- u=j;
- MIN=d[j];
- }
- }
- if(u==-1) return;
- vis[u]=true;
- for(int j=0;j<Adj[u].size();j++){
- int v=Adj[u][j].v;
- if(vis[v]==false && d[u] +Adj[u][j].dis <d[v]){
- d[v]=d[u]+Adj[u][j].dis;
- }
- }
- }
- }
若要求输出最短路径, 以邻接矩阵为例:
- const int maxv=1000;
- const int INF=1000000000;
- int n,G[maxv][maxv];
- int d[maxv]; // 起点到各点的最短路径长度
- bool vis[maxv]={false};
- int pre[maxv];
- void Dijkstra(int s){ //s 为起点
- fill(d,d+maxv,INF);
- for(int i=0;i<n;i++) pre[i]=i;
- d[s]=0;
- for(int i=0;i<n;i++){ // 循环 n 次
- int u=-1,MIN=INF; //u 使 d[u] 最小, MIN 存放最小 d[u]
- for(int j=0;j<n;j++){
- if(vis[j]==false && d[j]<MIN){ // 未收录的顶点中到起点距离最小者
- u=j;
- MIN=d[j];
- }
- }
- // 找不到小于 INF 的 d[u], 说明剩下的顶点和起点 s 不连通
- if(u==-1) return;
- vis[u] =true;
- for(int v=0;v<n;v++){
- if( G[u][v]!=INF && vis[v]==false && d[u]+G[u][v] <d[v]){
- d[v]=d[u]+G[u][v];
- pre[v]=u;
- }
- }
- }
- }
- void DFS(int s,int v){ // 从终点开始递归
- if(v==s){ // 如果当前已经到达起点, 输出起点并返回
- printf("%d\n",s);
- }
- DFS(s,pre[v]);
- printf("%d\n",v);
- }
另外还有一种情况, 如果某个结点存在多个前驱结点, 那上面这种 pre 数组的方法就不再适用, 改成 vector 即可:
- const int maxv=1010;
- const int INF=1000000000;
- vector<int> pre[maxv];
- void Dijkstra(int s){
- fill(d,d+maxv,INF);
- d[s]=0;
- for(int i=0;i<n;i++){
- int u=-1,MIN=INF;
- for(int j=0;j<n;j++){
- if(vis[j]==false && d[j]<MIN){
- u=j;
- MIN=d[j];
- }
- }
- if(u==-1) return;
- vis[u]=true;
- for(int v=0;v<n;v++){
- if(vis[v]==false &&G[u][v]!=INF){
- if(d[u]+G[u][v]<d[v]){
- d[v]=d[u]+G[u][v];
- pre[v].clear();
- pre[v].push_back(u);
- }
- else if(d[u]+G[u][v]==d[v]){
- pre[v].push_back(u);
- }
- }
- }
- }
- }
当访问的结点是路径起点 st 时 (边界), 此时 tempPath 里存了整条路径 (倒序), 这时需要计算第二标尺 value 的值, 并与 optValue 比较, 若更优则更新 optValue 并把 path 覆盖.
- const int maxv=1010;
- const int INF=1000000000;
- int optValue;
- vector<int> path,tempPath;
- vector<int> pre[maxv];
- void Dijkstra(int s){
- fill(d,d+maxv,INF);
- d[s]=0;
- for(int i=0;i<n;i++){
- int u=-1,MIN=INF;
- for(int j=0;j<n;j++){
- if(vis[j]==false && d[j]<MIN){
- u=j;
- MIN=d[j];
- }
- }
- if(u==-1) return;
- vis[u]=true;
- for(int v=0;v<n;v++){
- if(vis[v]==false &&G[u][v]!=INF){
- if(d[u]+G[u][v]<d[v]){
- d[v]=d[u]+G[u][v];
- pre[v].clear();
- pre[v].push_back(u);
- }
- else if(d[u]+G[u][v]==d[v]){
- pre[v].push_back(u);
- }
- }
- }
- }
- }
- void DFS(int v){ //v 为当前访问结点
- if(v==st){
- tempPath.push_back(v);
- int value;
- (计算路径的 value)
- if(value 优于 optValue){
- path=tempPath;
- optValue=value;
- }
- tempPath.pop_back(); // 将刚加入的结点删除
- return;
- }
- tempPath.push_back(v);
- for(int i=0;i<pre[v].size();i++){
- DFS(pre[v][i]);
- }
- tempPath.pop_back();
- }
除此之外, 还会碰到第二标尺, 常见有以下三种:(具体代码见晴神算法笔记, 写的很清楚)
新增边权 (如增加开销)
新增点权 (如收集到的物资)
求最短路径条数
来源: http://www.bubuko.com/infodetail-2964514.html