迪杰斯特拉算法百度百科定義：傳送門

gh大佬博客：傳送門

迪杰斯特拉算法用來計(jì)算一個(gè)點(diǎn)到其他所有點(diǎn)的最短路徑，是一種時(shí)間復(fù)雜度相對(duì)比較優(yōu)秀的算法 O（n²）（相對(duì)于Floyd算法來說）

是一種單源最短路徑算法，但是它并不能處理負(fù)邊權(quán)的情況

Dijkstra的算法思想：①將一開始所有的非源點(diǎn)到源的距離設(shè)置成無限大（你認(rèn)為的無限大實(shí)際上是0x3f(int)或者0x7fffffff(long long)），然后源到源距離設(shè)置成0（不就是0嗎），然后每次找到一個(gè)距離源最短的點(diǎn)u，將其變成白點(diǎn)，枚舉所有的藍(lán)點(diǎn)，如果源到白點(diǎn)存在中轉(zhuǎn)站——一個(gè)藍(lán)點(diǎn)使得源->藍(lán)點(diǎn)和藍(lán)點(diǎn)->白點(diǎn)的距離和更短，就更新。②每找到一個(gè)白點(diǎn)，就嘗試更新其他藍(lán)點(diǎn)，直到更新完畢。

代碼及注釋：

#include<cstdio> #include<iostream> #include<cstdlib> #include<iomanip> #include<cmath> #include<cstring> #include<string> #include<algorithm> #include<time.h> #include<queue> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pr; const double pi=acos(-1); #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define Rep(i,u) for(int i=head[u];i;i=Next[i]) #define clr(a) memset(a,0,sizeof a) #define pb push_back #define mp make_pair #define fi first #define sc second ld eps=1e-9; ll pp=1000000007; ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;} ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;} ll read(){ll ans=0;char last=' ',ch=getchar();while(ch<'0' || ch>'9')last=ch,ch=getchar();while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();if(last=='-')ans=-ans;return ans; }//快讀 //headconst int maxn=5001; int g[maxn][maxn];//g數(shù)組用來存儲(chǔ)圖; int n,m,s;//分別表示點(diǎn)的個(gè)數(shù)、有向邊的個(gè)數(shù)、出發(fā)點(diǎn)的編號(hào); bool vis[maxn];//表示是否已經(jīng)到達(dá)過; int d[maxn];//d[i]表示從詢問點(diǎn)到點(diǎn)i的最短路徑; const int inf=2147483647;int main () {n=read(),m=read(),s=read();rep(i,1,n){d[i]=inf;rep(j,1,n)g[i][j]=inf;g[i][i]=0;//自己到自己的最短路徑當(dāng)然是0 }//初始化數(shù)組; rep(i,1,m){int u=read(),v=read(),w=read();//u,v,i分別表示第i條有向邊的出發(fā)點(diǎn)、目標(biāo)點(diǎn)和長度;g[u][v]=w;//讀入; }vis[s]=1;//將起點(diǎn)標(biāo)記成已經(jīng)到達(dá); rep(i,1,n)d[i]=g[s][i];//將最短路徑初始化;//如果兩點(diǎn)之間有路線就初始化為該距離，如果沒有就還是inf;while(1){int stt_node=0,stt_dis=inf;//stt=shortest 初始化兩個(gè)變量 // stt_node表示最短路徑的終點(diǎn)，stt_dis表示最短路徑的長度 rep(i,1,n){ if(vis[i]==0&&d[i]<stt_dis)//如果該點(diǎn)還沒有到達(dá)，并且他的距離小于最短距離 {stt_node=i,stt_dis=d[i];//更新變量 }}if(stt_node==0) break;//如果已經(jīng)沒有可以更新的最短路徑了，就說明已經(jīng)結(jié)束了 vis[stt_node]=1;//將該點(diǎn)標(biāo)記成已經(jīng)到達(dá) rep(i,1,n){if(vis[i]||g[stt_node][i]==inf)continue;//如果并沒有到達(dá)或者是兩點(diǎn)之間沒有路徑，就進(jìn)入下一層循環(huán) d[i]=min(d[i],stt_dis+g[stt_node][i]);//更新最短路徑 }}rep(i,1,n)printf("%d ",d[i]);return 0; }

我們考慮一下對(duì)它的優(yōu)化。因?yàn)槿绻覀兠恳淮味家獟咭槐榕袛喑鲞?#xff0c;我們還不如直接存出邊：

鄰接表！（鏈?zhǔn)角跋蛐?#xff09;

#include<cstdio> #include<iostream> #include<cstdlib> #include<iomanip> #include<cmath> #include<cstring> #include<string> #include<algorithm> #include<time.h> #include<queue> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pr; const double pi=acos(-1); #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define Rep(i,u) for(int i=head[u];i;i=Next[i]) #define clr(a) memset(a,0,sizeof a) #define pb push_back #define mp make_pair #define fi first #define sc second ld eps=1e-9; ll pp=1000000007; ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;} ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;} ll read(){ll ans=0;char last=' ',ch=getchar();while(ch<'0' || ch>'9')last=ch,ch=getchar();while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();if(last=='-')ans=-ans;return ans; }//快讀 //headconst ll INF = 2147483647; struct edge {ll to, dis_, next; } Edge[9999999]; struct node {ll to, dis;inline friend bool operator<(const node &a, const node &b){return a.dis < b.dis;} }; ll head[9999999], dis[9999999]; bool vst[9999999]; ll nodenum, edgenum, origin_node, cnt = 1, t; priority_queue<node> q;inline void add_edge(ll from, ll to, ll value) {Edge[cnt].to = to;Edge[cnt].dis_ = value;Edge[cnt].next = head[from];head[from] = cnt++; }inline void dijkstra() {for (register int i = 1; i < origin_node; i++){dis[i] = INF;}//dis[origin_node]=0;for (register int i = origin_node + 1; i <= nodenum; i++){dis[i] = INF;}q.push((node){origin_node, 0});while (!q.empty()){int x = q.top().to;q.pop();if (vst[x])continue;vst[x] = 1;for (register int i = head[x]; i; i = Edge[i].next){dis[Edge[i].to] = min(dis[Edge[i].to], dis[x] + Edge[i].dis_);q.push((node){Edge[i].to, dis[Edge[i].to]});}} }int main() {nodenum = read(), edgenum = read(), origin_node = read() ;//t=read();for (register int i = 1; i <= edgenum; i++){register int f, t, v;f = read(), t = read(), v = read();add_edge(f, t, v);}dijkstra();rep(i,1,nodenum){printf("%lld ",dis[i]);}return 0; }

?

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/lcezych/p/10739866.html

總結(jié)

以上是生活随笔為你收集整理的Dijkstra算法——计算一个点到其他所有点的最短路径的算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。