spfa演算法c

① 一道信息學奧賽題，要詳細過程，好的加分，今天之內必須給答案，晚了不給分啊

這個其實就是最標準的單源最短路問題，這個有個極其簡單的做法。就說下floyed演算法首先讀入鄰接矩陣g( i, j )。表示從第i個車站到第j個車站的距離，不連通的就把距離設成一個非常大的數，比如0xfffffff。當然也要注意由於道路是雙向的，g( j, i ) = g( i, j )准備工作完成，該開始dp了這里的代碼太簡單了。。。推薦你背下來
for ( k = 1; k <= n; k++ )
for ( i = 1; i <= n; i++ )
{
if ( i == k ) continue;
for ( j = 1; j <= n; j++ )
{
if ( j == i || j == k ) continue;
if ( g[ i ][ k ] + g[ k ][ j ] < g[ i ][ j ] )
g[ i ][ j ] = g[ i ][ k ] + g[ k ][ j ];
}
}這個方程比較麻煩，就不寫了，復雜度是O(n^3)最後的最短路結果就是g[ 1 ][ n ]要求最少成車次數就把除了不連通的地方的權值都改成1，再進行一次floyed就可以了

對不起我沒注意- -
這樣的話可以構建一個新圖
把每條公交線路看成一個節點，把相交的公交線路連上一條邊，把起點和經過起點的線路相連（注意權值是1），終點和經過終點的線路相連（注意權值是0），兩條相交的公交線路權值設成1，這樣再做次floyed即可

② 求SPFA演算法的C語言標程，在線等！越簡單越好！

希望對你有幫助(^_^)
#include<stdio.h>
#include<stdlib.h>
int u[150005]={0},v[150005]={0},w[150005]={0},q[30005]={1},d[30005]={0},first[30005]={0},next[150005]={0},hash[30005]={0,1};
int main()
{
int n,e,head=0,tail=1,i,j;
scanf("%d%d",&n,&e);
e*=2;
for(i=2;i<=n;i++)
d[i]=1000000000;
for(i=1;i<=e;i++)
{
if(i%2==1) scanf("%d%d%d",&u[i],&v[i],&w[i]);
else
{
u[i]=v[i-1];
v[i]=u[i-1];
w[i]=w[i-1];
}
next[i]=first[u[i]];
first[u[i]]=i;
}
while(head!=tail)
{
for(i=first[q[head]];i!=0;i=next[i])
{
if(d[v[i]]>d[q[head]]+w[i])
{
d[v[i]]=d[q[head]]+w[i];
if(hash[v[i]]==0)
{
hash[v[i]]=1;
q[tail]=v[i];
tail=(tail+1)%(n+1);
}
}
}
hash[q[head]]=0;
head=(head+1)%(n+1);
}
printf("%d",d[n]);
//system("pause");
return 0;
}

③ 圖遍歷演算法之最短路徑Dijkstra演算法

最短路徑問題是圖論研究中一個經典演算法問題，旨在尋找圖中兩節點或單個節點到其他節點之間的最短路徑。根據問題的不同，演算法的具體形式包括：

常用的最短路徑演算法包括：Dijkstra演算法，A 演算法，Bellman-Ford演算法，SPFA演算法（Bellman-Ford演算法的改進版本），Floyd-Warshall演算法，Johnson演算法以及Bi-direction BFS演算法。本文將重點介紹Dijkstra演算法的原理以及實現。

Dijkstra演算法，翻譯作戴克斯特拉演算法或迪傑斯特拉演算法，於1956年由荷蘭計算機科學家艾茲赫爾.戴克斯特拉提出，用於解決賦權有向圖的 單源最短路徑問題 。所謂單源最短路徑問題是指確定起點，尋找該節點到圖中任意節點的最短路徑，演算法可用於尋找兩個城市中的最短路徑或是解決著名的旅行商問題。

問題描述 ：在無向圖 中， 為圖節點的集合， 為節點之間連線邊的集合。假設每條邊 的權重為 ，找到由頂點 到其餘各個節點的最短路徑（單源最短路徑）。

為帶權無向圖，圖中頂點 分為兩組，第一組為已求出最短路徑的頂點集合（用 表示）。初始時 只有源點，當求得一條最短路徑時，便將新增頂點添加進 ，直到所有頂點加入 中，演算法結束。第二組為未確定最短路徑頂點集合（用 表示），隨著 中頂點增加， 中頂點逐漸減少。

以下圖為例，對Dijkstra演算法的工作流程進行演示（以頂點 為起點）：

註：
01） 是已計算出最短路徑的頂點集合；
02） 是未計算出最短路徑的頂點集合；
03） 表示頂點 到頂點 的最短距離為3
第1步 ：選取頂點 添加進

第2步 ：選取頂點 添加進 ，更新 中頂點最短距離

第3步 ：選取頂點 添加進 ，更新 中頂點最短距離

第4步 ：選取頂點 添加進 ，更新 中頂點最短距離

第5步 ：選取頂點 添加進 ，更新 中頂點最短距離

第6步 ：選取頂點 添加進 ，更新 中頂點最短距離

第7步 ：選取頂點 添加進 ，更新 中頂點最短距離

示例：node編號1-7分別代表A,B,C,D,E,F,G

(s.paths <- shortest.paths(g, algorithm = "dijkstra"))輸出結果：

(s.paths <- shortest.paths(g,4, algorithm = "dijkstra"))輸出結果：

示例：

找到D（4）到G（7）的最短路徑：

[1] 維基網路，最短路徑問題： https://zh.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98 ；
[2]CSDN，Dijkstra演算法原理： https://blog.csdn.net/yalishadaa/article/details/55827681 ;
[3]RDocumentation: https://www.rdocumentation.org/packages/RNeo4j/versions/1.6.4/topics/dijkstra ;
[4]RDocumentation: https://www.rdocumentation.org/packages/igraph/versions/0.1.1/topics/shortest.paths ;
[5]Pypi: https://pypi.org/project/Dijkstar/

④ spfa 怎麼解決 最長路的問題 （為無向圖且保證出現正環）

SPFA可以處理負環，記錄一個點出現的次數，只要這個點出現次數超過n次（n為總點數），就證明有負環

事實上，把正邊權改為負邊權是可以的，也很方便；但是有時SPFA可以直接修改演算法中的大於號或小於號，這不適用於Dijkstra

邊權取負是最常用的，題目一般會保證沒有負環，如果有的話一般會讓輸出impossible這樣的字串

下面是我SPFA的一個板子

#include<bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

struct Edge

{

int to,next,len;

}edge[(int)1e5+5];

struct Node

{

int head,dis;

bool vis;

}node[(int)1e5+5];

int cnt;

int addEdge(int u,int v,int w)

{

edge[++cnt].len=w;

edge[cnt].to=v;

edge[cnt].next=node[u].head;

node[u].head=cnt;

}

int u,v,w;

int n,m;

int SPFA()

{

queue<int>q;

for(int i=1;i<=n;i++)

{

node[i].dis=INF;

node[i].vis=false;

}

node[1].dis=0;

node[1].vis=true;

q.push(1);

while(not q.empty())

{

int u=q.front();

q.pop();

node[u].vis=false;

for(int e=node[u].head;e;e=edge[e].next)

{

int v;

if(node[v=edge[e].to].dis<=node[u].dis+edge[e].len)continue;

node[v].dis=node[u].dis+edge[e].len;

/*只要在這里加一個判斷，

• c[v]++;//更新出現次數

• if(c[v]>n) return 0;*/

if(!node[v].vis)

{

q.push(v);

node[v].vis=true;

}

}

}

if(node[n].dis==INF)

{

puts("impossible");

exit(0);

}

return node[n].dis;

}

int main()

{

cin>>n>>m;

for(int i=1;i<=m;i++)

{

cin>>u>>v>>w;

addEdge(u,v,w);//根據題目要求是否取相反數

}

cout<<SPFA()<<endl;

return 0;

}

純手打，很累，不理解繼續問，求採納

⑤ 有些圖論題數據太大無法用鄰接矩陣，所以請教教我怎麼用數組模擬鄰接表建圖（帶權）。（C/C++代碼）

暫且與例題一起的
路徑(netbar.pas)

綿陽中學以人數眾多而聞名。三個年級共有 10000 多人，學生多了附近的網吧也多。
Mzoiers 都熱衷於 Dota，可學校的機子配置相當差(評測伺服器除外)，根本不能玩
Dota，那就只有去網吧。星期天到星期五都是晚上 10：20 才下晚自習，幾乎沒時間玩。
然而星期六下午放假是絕好的時間，但是學校人多啊，一放學去網吧的人就開始狂奔，競爭
之激烈，搶到機子的難度非常之大。往往在我們到達網吧之前都坐滿了。
學校到網吧的路是錯綜復雜的，以致於到一個自己想去的網吧都有非常多的路線可以選
擇，而路線的長度又不相同，這樣就決定了要花費的時間，因此想要盡快到達，選擇一條最
佳的線路是很有必要的。
【問題描述】
為了簡化問題，我們把學校與周邊的網吧看做圖中的頂點，學校與網吧，網吧與網吧之
間的路線看做邊，每個邊都有一個權，表示我們走完這條路的時間，由於放學人流量大，如
果反向走會有危險，因此這是一個有向圖。
我的學校在 S 點，想要去的網吧在 T 點。你的任務就是選擇一條最佳路線，使得從
學校到目的地網吧的時間最短，你只需要輸出最短到達時間即可。
【輸入文件】
netbar.in 中共有 M+2 行數據
第一行兩個整數 N，M，表示點數和邊數。
然後 M 行每行 3 個正整數(u，v，t)，表示有一條可由 u 到 v 耗時為 t 的邊。
最後一行兩個正整數 S、T。
【輸出文件】
netbar.out 中，只有一行，一個整數表示最短時間。如果 S、T 之間不存在通路則輸
出「No Solution!」(雙引號不輸出，「!」為西文標點)。
【輸入樣例】
4 4
1 2 3
2 4 10
1 3 5
3 4 5
1 4
【輸出樣例】
10
【數據規模】
對於 30％的數據保證有 1<N<=1000，1<=M<=1000；
對於全部的數據保證有 1<N<=10000，1<=M<=100000。

解題思路：
題目可以抽象為輸入n個頂點，e條邊的有向圖，再讀入源點S和目標點T，求S到T的最短路。輸入規模：1<N<=10000，1<=M<=100000。
最短路有三種方法：floyd,dijsktra,spfa。如果用floyd,時間性能為O(n3) , 只能通過1000以內的數據；用dijkstra，時間性能為O(n2) ，只能通過10000以內的數據，且用鄰接矩陣存儲時，10000*10000*4個位元組，總內存達到380多MB，會超內存。用spfa演算法，時間性能為O(kM)，能通過所有測試數據，k的值平均為2，表示頂點入隊的平均次數。此時，可以採用數組模擬鏈表的存邊方法，開一個邊的一維數組，把所有邊存儲起來。如對於如下輸入數據：
5 7
1 2 2
1 5 8
1 3 1
1 4 3
2 5 3
3 5 1
4 3 2
1 5
下面這個圖的數組模擬鏈表的形式存儲邊，把從某個頂點出來的所有邊通過鏈表的形式，鏈接起來，就象存儲普通有序樹一樣，右兒子掛到左兒子下面。這里的操作原理是，處理某個頂點出來的邊時，下一條邊掛到前一條邊，如下圖，第一條邊指向0，後面的邊都指向前一條邊，所以，在處理某個頂點相連的邊的松馳操作時，可以很方便的處理以該頂點連出去的邊，當指向0時，則以該 頂點出去的松馳操作完成。

program netbar;
var
list,dis:array [0..10000] of longint; //list存儲當前邊的指針,dis存儲各點到源點的最短路
next,toit,cost,q:array [0..100000] of longint;//next存儲當前邊指向前一條邊的位置，toit表示當前邊的出點，cost表示當前邊的邊權
n,m,i,a,b,c,s,e,tot:longint;
flag:array [0..10000] of boolean;
procere add(a,b,c:longint);//數組模擬鏈表的添邊的方法
begin
inc(tot); //邊的數目
toit[tot]:=b; //當前邊的出點頂點標號
cost[tot]:=c; //當前邊的權值
next[tot]:=list[a]; //當前邊指向前一條邊的位置，如果當前邊是頂點a的讀入的第一條邊，則它指向前面第0條邊，表示next[tot]:=0。
list[a]:=tot; //從入點a引出的邊的編號存儲給lsit[a]
end;
procere SPFA;
var
i,head,tail,v,k:longint;
begin
fillchar(flag,sizeof(flag),true);
for i:=1 to n do dis[i]:=maxlongint;
head:=1; tail:=1; q[1]:=s; dis[s]:=0; flag[s]:=false;//源點s入隊
repeat
v:=q[head]; k:=list[v]; //隊列頭出隊，k存儲當前v頂點的邊的編號
while k<>0 do //處理v的所有邊，直至邊指向0，即第一條邊也處理了
begin
if dis[v]+cost[k]<dis[toit[k]] then //松馳操作
begin
dis[toit[k]]:=dis[v]+cost[k]; //松馳成功
if flag[toit[k]] then //入隊
begin
inc(tail); q[tail]:=toit[k]; flag[toit[k]]:=false;
end;
end;
k:=next[k]; //處理頂點v的前一條邊
end;
flag[v]:=true;
inc(head);
until head>tail;
end;
begin
assign(input,'netbar.in'); reset(input);
assign(output,'netbar.out'); rewrite(output);
fillchar(list,sizeof(list),0);
fillchar(next,sizeof(next),0);
fillchar(toit,sizeof(toit),0);
fillchar(cost,sizeof(cost),0);
tot:=0;
readln(n,m);
for i:=1 to m do
begin readln(a,b,c); add(a,b,c); end;
readln(s,e);
SPFA;
if dis[e]<maxlongint then writeln(dis[e])
else writeln('No Solution!');
close(input); close(output);
end.

當N的頂點規模達到10000時，如果用鄰接矩陣存儲圖，容易超內存，且1個億的運算次數在1S的時限內不一定出得來。

不好意思 這邊只有PASCAL 的 暫且將就吧 C語言的MS沒有額……

⑥ 求解：圖論中常見的最短路徑演算法有幾種都是什麼

主要是有三種、、

第一種是最直接的貪心dijkstra演算法、、可以利用堆數據結構進行優化、、缺點就是不能求有負權的最短路與判斷負環、、

第二種是bellman-ford演算法、、根據鬆弛操作的性質是可以來判斷負環的、、時間復雜度是O(nm)的、、

第三種是SPFA演算法、、把他單獨拿出來作為一種演算法並不是非常好的、、他的實質應該是上面的bellman-ford演算法的隊列優化時間復雜度更低、O(KE)、K的值約等於2、、

⑦ SPFA演算法的pascal代碼

constmaxp=10000;{最大結點數}var{變數定義}p,c,s,t:longint;{p,結點數;c,邊數;s:起點;t:終點}a,b:array[1..maxp,0..maxp]oflongint;{a[x,y]存x,y之間邊的權;b[x,c]存與x相連的第c個邊的另一個結點y}d,m:array[1..maxp]ofinteger;{d:隊列,m:入隊次數標記}v:array[1..maxp]ofboolean;{是否入隊的標記}dist:array[1..maxp]oflongint;{到起點的最短路}head,tail:longint;{隊首/隊尾指針}procereinit;vari,x,y,z:longint;beginread(p,c);fori:=1tocdobeginreadln(x,y,z);{x,y:一條邊的兩個結點;z:這條邊的權值}inc(b[x,0]);b[x,b[x,0]]:=y;a[x,y]:=z;{b[x,0]：以x為一個結點的邊的條數}inc(b[y,0]);b[y,b[y,0]]:=x;a[y,x]:=z;end;readln(s,t);{讀入起點與終點}end;procerespfa(s:longint);{SPFA}vari,j,now,sum:longint;beginfillchar(d,sizeof(d),0);fillchar(v,sizeof(v),false);forj:=1topdodist[j]:=maxlongint;dist[s]:=0;v[s]:=true;d[1]:=s;{隊列的初始狀態,s為起點}head:=1;tail:=1;whilehead<=taildo{隊列不空}beginnow:=d[head];{取隊首元素}fori:=1tob[now,0]doifdist[b[now,i]]>dist[now]+a[now,b[now,i]]thenbegindist[b[now,i]]:=dist[now]+a[now,b[now,i]];{修改最短路}ifnotv[b[now,i]]then{擴展結點入隊}begininc(m[b[now,i]]);ifm[b[now,i]])=pthenbeginwriteln('noway');halt;end;{同一節點入隊次數超過p，存在負環}inc(tail);d[tail]:=b[now,i];v[b[now,i]]:=true;end;end;v[now]:=false;{釋放結點，一定要釋放掉，因為這節點有可能下次用來鬆弛其它節點}inc(head);{出隊}end;end;procereprint;beginwriteln(dist[t]);end;begininit;spfa(s);print;end.

⑧ 一道c語言的題目

type ss=record
a,b,c,next:longint;
end;
var n,m,i,j,rp,k,x,y,tot,z:longint;
im:boolean;
map:array[0..200001] of ss;
q:array[0..100001] of longint;
s,a:array[0..50001] of longint;
f:array[0..50001] of boolean;
d:array[0..5] of longint;
l:array[0..5,0..5] of longint;
dp:array[0..5,0..63] of longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procere swap(var a,b:longint);
var t:longint;
begin
t:=a; a:=b; b:=t;
end;
procere jia(x,y,z:longint);
begin
inc(tot);
map[tot].a:=x;
map[tot].b:=y;
map[tot].c:=z;
map[tot].next:=a[x];
a[x]:=tot;
end;
function spfa(x,y:longint):longint;
var h,t,temp,i,j,p,d,hh,tt:longint;
begin
fillchar(f,sizeof(f),false);
fillchar(s,sizeof(s),$7f);
s[x]:=0;
h:=1;
hh:=1;
tt:=1;
t:=1;
f[x]:=true;
q[1]:=x;
repeat
temp:=q[h];
f[q[h]]:=false;
inc(h);
if h>100000 then h:=1;
inc(hh);
p:=a[temp];
while p<>-1 do
begin
if s[map[p].b]>s[temp]+map[p].c then
begin
s[map[p].b]:=s[temp]+map[p].c;
if not(f[map[p].b]) then
begin
if s[map[p].b]<=s[q[h]] then
begin
dec(h);
dec(hh);
if h<1 then h:=100000;
q[h]:=map[p].b;
end
else
begin
inc(t);
inc(tt);
if t>100000 then t:=1;
q[t]:=map[p].b;
end;
f[map[p].b]:=true;
end;
end;
p:=map[p].next;
end;
until hh>tt;
exit(s[y]);
end;
begin
readln(n,m);
for i:=1 to 5 do
read(d[i]);
d[0]:=1;
fillchar(a,sizeof(a),255);
for i:=1 to m do
begin
read(x,y,z);
jia(x,y,z);
jia(y,x,z);
end;
rp:=maxlongint;
for i:=0 to 4 do
for j:=i+1 to 5 do
begin
l[i,j]:=spfa(d[i],d[j]);
l[j,i]:=l[i,j];
end;
fillchar(dp,sizeof(dp),$7f);
dp[0,1]:=0;
repeat
im:=false;
for i:=1 to 5 do
for j:=0 to 5 do
if i<>j then
for k:=((1 shl i)+(1 shl j)) to 63 do
if dp[i,k]>dp[j,k-1 shl i]+l[j,i] then
begin
dp[i,k]:=dp[j,k-1 shl i]+l[j,i];
im:=true;
end;
until not(im);
for i:=1 to 5 do
rp:=min(rp,dp[i,63]);
writeln(rp);
end.