• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

核心:两层循环:

问:为什么要循环n-1次

答:有n个点,若求a到b的最短路径,至多经过n-1个点(不能是回路)

贝尔曼福特不能解决负权回路问题:

如果为负权回路:每次判断是否松弛操作时,都有dis[u] wdis[v]

因此每次都会减小,从而无法正确的求出最短路径

1 #包含位/标准位

2使用命名空间标准

3 const int maxn=1000

4 const int INF=0x 3 F3 F3 F3 f;

5 int w[maxn],u[maxn],v[maxn],dis[maxn],back[maxn];

6 int检查

7 int m,n;

8 void dfs(int back[],int k)

9 {

10 if(back[k]==k)

11 {

12 coutk

13返回;

14 }

15 dfs(back,back[k]);

16 coutk

17返回;

18 }

19虚空贝尔曼_福特()

20 {

21 for(int I=1;I=n;我)

22 {

23回=I;

24 dis=INF;

25 }

26 dis[1]=0;

27 for(int j=1;j=n-1;j)

28 {

29检查=0;

30 for(int I=1;I=m;我)

31 {

32 if(dis[u]!=infdis[v]dis[u] w)

33 {

34 dis[v]=dis[u]w

35 back[v]=u

36检查=1;

37 }

38 }

39如果(检查==0)

40破;

41 }

42 }

43 int main()

44 {

45 int flag=0;

46 cinnm

47 for(int I=1;I=m;我)

48 {

49 cinuvw

50 }

51贝尔曼_福特();

52 for(int j=1;j=n-1;j)

53 {

54 for(int I=1;I=m;我)

55 {

56 if(dis[v]dis[u] w)

57 {

58旗=1;

59破;

60 }

61 }

62 }

63如果(标志==1)

64 cout '有负权回路恩德尔

其他65个

66 {

67 for(int I=1;I=n;我)

68 {

69 cout'1号顶点到我号顶点的最短距离为disendl;

70 }

71 cout'1号节点到5号节点的路径为:';

72个dfs(背,5);

73 }

74返回0;

75 }

dfxyuuxtpo53239.png

lugm4jg4rrr3240.png

用队列优化贝尔曼福特算法:

队列优化后的板英尺(板脚)算法,遇到负权回路会死循环

注释内是用数组模拟队列的方法

1 #包含位/标准位

2使用命名空间标准

3 const int INF=0x 3 F3 F3 F3 f;

4 const int maxn=10001

5 int u[maxn],v[maxn],w[maxn];

6 int first[maxn],next[maxn],book[maxn];

7//int que[maxn];

8 int dis[maxn];

9 int n,m,k;//head=1,tail=1;

10队列int q;

11虚空贝尔曼_福特()

12 {

13//que[tail]=1;

14//尾巴;

15问推(1);

16本书[1]=1;

17 dis[1]=0;

18 while(/*headtail*/!q.empty())

19 {

20//k=first[que[head]];

21k=first[q . front()];

22 while(k!=-1)

23 {

24 if(dis[v[k]]dis[u[k]] w[k])

25 {

26 dis[v[k]]=dis[u[k]]w[k];

27

28 if(book[v[k]]==0)

29 {

30//que[tail]=v[k];

31//尾巴;

32 q . push(v[k]);

33 book[v[k]]=1;

34 }

35k=下一个[k];

36 }

37 }

38//que[head]=0;

39//头;

40 q . pop();

41 }

42 }

43 int main()

44 {

45填充(第一个,第一个10001,-1);

46填充(dis,dis 10001,INF);

47 cinnm

48 for(int I=1;I=m;我)

49 {

50 cinuvw

51 next=first[u];

52第一个[u]=I;

53 }

54贝尔曼_福特();

55 for(int I=1;I=n;我)

56 {

57 cout dis' ';

58 }

59返回0;

60 }

无负权回路:

iaxzo5wf0bi3241.png

有负权回路:

sm1v35aiebk3242.png

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now