最短路的求法，有很多，Floyd、Dijkstra、Bellma-Ford，但是我們來思考一下最長路，SPFA和Floyd必然可以跑最長路，一個是DP，一個是基于更新的更新，所以由于這兩種特性，決定了他們能夠跑最長路，但是最不會被卡的Dijkstra在這里就顯得蹩腳了。
為什么？我們來看一下這種情況：

最長路更新的話，最先出隊的是1-4邊，但是她不能更松弛別人，此時1-4邊=3
然后1-3出隊，他能松弛1-4 此時1-3為2 1-4為5
然后1-2出隊，他能松弛1-3 此時1-2為1 1-3 為3
但是3不能再入隊松弛別人了。
所以導致了答案錯誤。
想一下
為什么能跑最短路，因為路徑長度不減，這是算法的核心，而到了最長路，理應是路徑長度不增，但是我們看到我們確定邊的過程為 3 2 5 1 3不滿足單調性，所以必然錯誤。
這是時候有人就要說了，那我們為什么不去掉vis數組呢，那么算法就要退化，復雜度變成了什么？最壞$n^{2}log{n}^2=2n^{2}logn$這不就成了bfs了嗎???
我在這里提出一種優化，但是僅限于路徑長度較短的情況下，Node中多加一個double類型的數據記錄長度分之一，用來跑最短路，但是由于精度的限制1e6數據就開始發飄。

//dijkstra 去掉VIS數組 #include<bits/stdc++.h> using namespace std; const int INF=0x3f3f3f3f; typedef long long ll; typedef pair<int,int> PII; struct Node {int var,next,val; } edge[100000005]; int head[100005],tot,dis[100005],N,M; bool vis[100005]; priority_queue<PII> Q; void add(int a, int b, int c) {edge[++tot].var = b;edge[tot].val = c;edge[tot].next = head[a];head[a] = tot; } void init()//多組輸入調用 {tot=0;memset(head,0,sizeof(head)); } void dijkstra(int s) {for(int i=0;i<=N;i++)dis[i]=-INF;//memset(vis,0,sizeof(vis));//while(Q.size()) Q.pop();dis[s] = 0;Q.push(make_pair(0,s));while(!Q.empty()){int x=Q.top().second;Q.pop();if(vis[x])continue;//vis[x]=1;for(int i=head[x]; i; i=edge[i].next){int y=edge[i].var;if(dis[x]+edge[i].val>dis[y]){dis[y]=dis[x]+edge[i].val;//if(!vis[y])Q.push(make_pair(dis[y],y));}}} } int main() {int S;scanf("%d %d",&N,&M);while(M--){int x,y,z;scanf("%d %d %d",&x,&y,&z);add(x,y,z);}dijkstra(1);if(dis[N]!=-INF) cout<<dis[N]<<endl;else cout<<-1<<endl;return 0; } //SPFA #include<iostream> #include<queue> #include<algorithm> #include<set> #include<cmath> #include<vector> #include<map> #include<stack> #include<bitset> #include<cstdio> #include<cstring> #define Swap(a,b) a^=b^=a^=b #define cini(n) scanf("%d",&n) #define cinl(n) scanf("%lld",&n) #define cinc(n) scanf("%c",&n) #define cins(s) scanf("%s",s) #define coui(n) printf("%d",n) #define couc(n) printf("%c",n) #define coul(n) printf("%lld",n) #define speed ios_base::sync_with_stdio(0) #define Max(a,b) a>b?a:b #define Min(a,b) a<b?a:b #define mem(n,x) memset(n,x,sizeof(n)) #define INF 0x3f3f3f3f #define maxn 100010 #define Ege 100000000 #define Vertex 1005 #define esp 1e-9 #define mp(a,b) make_pair(a,b) using namespace std; typedef long long ll; typedef pair<int,int> PII; struct Node {int to, lat, val; //邊的右端點，邊下一條邊，邊權 }; Node edge[1000005]; int head[1005],tot,dis[1005],N,M,vis[1005]; void add(int from, int to, int dis) {edge[++tot].lat = head[from];edge[tot].to = to;edge[tot].val = dis;head[from] = tot;} void spfa(int s) {for(int i=0;i<=N;i++) dis[i]=-INF;dis[0]=0;memset(vis, 0, sizeof(vis));vis[s] = 1;dis[s] = 0;queue<int>Q;Q.push(s);while (!Q.empty()){int u = Q.front();Q.pop();vis[u] = 0;for (int i = head[u]; i; i = edge[i].lat){int to = edge[i].to;int di = edge[i].val;if (dis[to]<dis[u] + di){dis[to] = dis[u] + di;if (!vis[to]){vis[to] = 1;Q.push(to);}}}}} int main() {int t, x;memset(head, 0, sizeof(head));cini(N),cini(M);while (M--){int a, b, dis;scanf("%d %d %d", &a, &b, &dis);add(a, b, dis);}spfa(1);if(dis[N]==-INF) {return cout<<-1<<endl,0;}cout<<dis[N]<<endl;return 0; }

總結

以上是生活随笔為你收集整理的图论--关于最长路的探讨的全部內容，希望文章能夠幫你解決所遇到的問題。

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