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.