【最短路算法】Dijkstra知識點&代碼

代碼：

#include<iostream>
#include<vector>
#include<cstdio>
#include<queue>
#include<map>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<set>
#include<cstring>
using namespace std;
typedef long long ll;
const ll INF=2147483647;
const int MM=500002;
const int NM=10002;
int n,m,s;//點,邊,起始
int dis[NM];//最小距離
bool book[NM];//記錄有沒有作為頂點搜尋過
//鍊式向前星
struct NODE{
    int to;
    int nxt;
    int c;
}node[MM];//鍊式向前星
int head[NM],lcnt=1;
void add(int a,int b,int c){
    node[lcnt].to=b;
    node[lcnt].c=c;
    node[lcnt].nxt=head[a];
    head[a]=lcnt++;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++){
        dis[i]=INF;
    }
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        //if(a==b)
        //    continue;

        add(a,b,c);
        //add(b,a,c);
    }
    for(int i=head[s];i;i=node[i].nxt){             //從起始點開始枚舉
        int idx=node[i].to;                           
        dis[idx]=min(node[i].c,dis[idx]);            //更新最短路
        
    }
    dis[s]=0;                   //自身距離為0 
    book[s]=1;                //标記搜尋過
    for(int kkk=1;kkk<n;kkk++){          //枚舉每個點(用編号)
        int minn=INF,u=0;
        for(int i=1;i<=n;i++){
            if(!book[i]&&dis[i]<minn){        
                u=i;                                 //枚舉每個已經被标記了但是沒有被搜尋過的點
                minn=dis[i];                      //找距離最小的
            }
        }
    
        
        /*for(int i=1;i<=n;i++){
            if(mp[u][i]<INF){
                dis[i]=min(dis[i],dis[u]+mp[u][i]);
            }
        }*/
        
        for(int i=head[u];i;i=node[i].nxt){
            int idx=node[i].to;                                //正在搜尋的點開始,枚舉每一條邊
            
            dis[idx]=min(dis[idx],dis[u]+node[i].c);      //更新最短距離,設f[i][j]為i到j的最大距離,d[i]為起始點到i的距離
                                                                    //得到    d[j]=min(d[j],d[i]+f[i][j])
        }
        
        book[u]=1;                                              //标記這個點搜尋過了
        
    }
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<" ";
    }
    return 0;
}

檢視神奇代碼

1.儲存方式：

鍊式向前星>> https://www.cnblogs.com/dudujerry/p/9915713.html

int n,m,s;//點,邊,起始
int dis[NM];//最小距離
bool book[NM];//記錄有沒有作為頂點搜尋過
//鍊式向前星
struct NODE{
	int to;
	int nxt;
	int c;
}node[MM];//鍊式向前星
int head[NM],lcnt=1;
void add(int a,int b,int c){
	node[lcnt].to=b;
	node[lcnt].c=c;
	node[lcnt].nxt=head[a];
	head[a]=lcnt++;
}

2.更新所有與根節點連接配接的最短路

for(int i=head[s];i;i=node[i].nxt){             //枚舉所有與起點連接配接的邊
	int idx=node[i].to;                           
　　　　　dis[idx]=min(node[i].c,dis[idx]);            //更新最短路
		
}
dis[s]=0;                   //自身距離為0 
book[s]=1;                //标記搜尋過

使用book記錄是否作為過用來更新的點，則搜完之後 book[s]=1

3.接下來枚舉除源點外所有點來作為用來更新最短路的點

依 ”從上次求出最短路的點中選出最短路最小的點“ 的順序周遊除源點以外的n-1個點

for(int kkk=1;kkk<n;kkk++){          //枚舉n-1次，因為原點已經被用來更新過了
		int minn=INF,u=0;
		for(int i=1;i<=n;i++){                  
			if(!book[i]&&dis[i]<minn){        //枚舉每個已經被标記了但是沒有被搜尋過的點
				u=i;                                 
				minn=dis[i];                      //找距離最小的
			}
		}
              . . .

4.從選出的點開始更新所有與它連接配接的邊

設已知源點到i點的距離dis[i] 和點i到點j的距離f[i][j] (未知目前dis [ j ]是否正确）

可以得到 dis [ j ] = min ( dis [ j ] , dis [ i ] + f [ i ] [ j ] )

根據上面的方程可以周遊所有與選出的點，算出最短路

　　　　　　　　　. . .
　　　　　　　　　 for(int i=head[u];i;i=node[i].nxt){
			int idx=node[i].to;                                //正在搜尋的點開始,枚舉每一條邊
			
			dis[idx]=min(dis[idx],dis[u]+node[i].c);      //更新最短距離,設f[i][j]為i到j的最大距離,d[i]為起始點到i的距離
			                                                        //得到    d[j]=min(d[j],d[i]+f[i][j])
		}
		
		book[u]=1;                                              //标記這個點搜尋過了
		
	}

5.輸出

dis [ i ]就是源點到i點的距離

for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}

轉載于:https://www.cnblogs.com/dudujerry/p/9915505.html

【最短路算法】Dijkstra知識點&amp;代碼

【最短路算法】Dijkstra知識點&代碼