Dij：貪心思想的單源最短路，時間復雜度O(n^2)。

Dij算法流程：

d數組記錄源點s到每個點的距離，若無邊則設為inf，標記源點；

選出d數組中未標記的最小值，該節點記為k，并標記k為已求出最短路；

枚舉每個節點(記為j)，若經過k到達j的路徑<d[j]且未標記，則更新d[j];

重復2、3步n次；

d[v]為s-v的最短路；

堆優Dij：即用堆優化的dij算法，時間復雜度O(nlogn);(但是據說跑起來比spfa快？求神犇解釋)

堆優Dij算法流程：

q為priority_queue,優先隊列記錄一個二元組，分別為索引位置和數值；

d數組記錄源點s到每個點的距離，若無邊則設為inf；

源點入隊；

隊首出隊并標記隊首；

遍歷隊首的鄰接點，若可松弛，則更新該鄰接點的最短路并將該節點壓入優先隊列；

不知道為什么，寫出來的spfa和堆優dij的唯一區別就是spfa的隊列變成了dij的優先隊列，也不知道這樣對不對，若有錯誤希望大家指出。

經測試，其實無需標記，堆優dij是照著dij模板改的，求解釋。。。

例題：Codevs2038香甜的黃油

1 #include<cstdio> 2 #include<cmath> 3 #include<queue> 4 #include<vector> 5 #include<cstring> 6 using namespace std; 7 8 struct edge{ 9 int to; 10 int w; 11 int next; 12 }; 13 14 struct node{ 15 int index,value; 16 node(){}; 17 node(int x,int y){index=x;value=y;}//構造函數 18 friend bool operator < (node a,node b){ 19 return a.value>b.value; 20 }//重載小于號 21 }; 22 23 priority_queue<node> q; 24 edge e[10000]; 25 int ne=0,head[1000],d[1000],a[1000],answer[1000]={0}; 26 bool b[1000]; 27 28 void add(int a,int b,int c){ 29 e[++ne].to=b;e[ne].w=c;e[ne].next=head[a];head[a]=ne; 30 } 31 32 void dij(int k){//k為源點編號 33 int i,v; 34 node u; 35 memset(d,127,sizeof(d)); 36 memset(b,0,sizeof(b));//初始化 37 d[k]=0; 38 //b[k]=true; 39 q.push(node(k,0));//構造并壓入源點 40 while(!q.empty()){ 41 u=q.top();q.pop();//彈出隊首 42 //if(b[u.index])continue; 43 //b[u.index]=true;//標記 44 for(i=head[u.index];i!=-1;i=e[i].next){//遍歷鄰接點 45 v=e[i].to; 46 if(u.value+e[i].w<d[v]/*&&b[v]==false*/){ 47 d[v]=u.value+e[i].w;//松弛操作 48 q.push(node(v,d[v]));//壓入新節點 49 } 50 } 51 } 52 } 53 54 int main(){ 55 int n,p,c,ans=999999999,i,j,u,v,w; 56 memset(head,-1,sizeof(head)); 57 memset(e,0,sizeof(e)); 58 scanf("%d%d%d",&n,&p,&c); 59 for(i=1;i<=n;i++)scanf("%d",&a[i]); 60 for(i=1;i<=c;i++){ 61 scanf("%d%d%d",&u,&v,&w); 62 add(u,v,w); 63 add(v,u,w);//連邊 64 } 65 for(i=1;i<=p;i++){ 66 dij(i); 67 int sum=0; 68 for(j=1;j<=n;j++)sum+=d[a[j]]; 69 ans=min(ans,sum); 70 } 71 printf("%d\n",ans); 72 }

?

?

?

轉載于:https://www.cnblogs.com/y-m-y/p/5730794.html

總結

以上是生活随笔為你收集整理的堆优DIJ模板的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。