Bellman‐Fordアルゴリズム単一ソース最短経路(o(nm))
解決した問題は依然としてA都市からB都市への最短経路を見つけることである.
Bellman-Fordアルゴリズムは、各頂点間の最短経路を探し出し、経路重み値は負数であってもよいが、負重み回路(この回路に負重み経路が存在する)は存在しない.Dijkstraアルゴリズムは、ある頂点から他の頂点への最短経路を探し出す.もちろんDijkstraは各頂点間の最短経路を探し出し、n回Dijkstraをすればよい.
構想:各ペアの頂点i,jに対して,iからjへの最短経路の重みを絶えず縮小する.i,jに頂点kを加え、iからk,kからjまでの経路の和がiからjまでの経路長より小さいか否かを判断し、kを加えた場合、iからjまでの経路長を調整する.
縮小の条件:a[i][j]>a[i][k]+a[k][j];(a:頂点ペアあたりのパス長)
次の2組のテスト配列は,前のグループが負の重み回路を構成しておらず,後のグループが負の重み回路であり,正確な結果が得られない.
第1グループ:
5 1 2 6 2 3 5 3 2 -2 5 3 -3 4 3 7 2 4 -4 5 4 9 1 5 7 4 1 2 2 5 8 0 0 0
2番目のグループ:
3 1 2 2 2 3 3 3 1 -8 0 0 0
Bellman-Fordアルゴリズムは、各頂点間の最短経路を探し出し、経路重み値は負数であってもよいが、負重み回路(この回路に負重み経路が存在する)は存在しない.Dijkstraアルゴリズムは、ある頂点から他の頂点への最短経路を探し出す.もちろんDijkstraは各頂点間の最短経路を探し出し、n回Dijkstraをすればよい.
構想:各ペアの頂点i,jに対して,iからjへの最短経路の重みを絶えず縮小する.i,jに頂点kを加え、iからk,kからjまでの経路の和がiからjまでの経路長より小さいか否かを判断し、kを加えた場合、iからjまでの経路長を調整する.
縮小の条件:a[i][j]>a[i][k]+a[k][j];(a:頂点ペアあたりのパス長)
次の2組のテスト配列は,前のグループが負の重み回路を構成しておらず,後のグループが負の重み回路であり,正確な結果が得られない.
第1グループ:
5 1 2 6 2 3 5 3 2 -2 5 3 -3 4 3 7 2 4 -4 5 4 9 1 5 7 4 1 2 2 5 8 0 0 0
2番目のグループ:
3 1 2 2 2 3 3 3 1 -8 0 0 0
#include<stdio.h>
#define MAX 10000
/* */
int
a[
100
]
[
100
]
;
/* */
int
path[
100
]
[
100
]
;
/* */
int
c[
100
]
[
100
]
;
void
Floyd(
int
n)
{
int
i,j,k;
/* a，path*/
for
(
i=
1
;
i<=
n;
++
i)
{
for
(
j=
1
;
j<=
n;
++
j)
{
if
(
c[
i]
[
j]
!
=
MAX)
{
path[
i]
[
j]
=
j;
}
else
{
path[
i]
[
j]
=
-
1
;
}
a[
i]
[
j]
=
c[
i]
[
j]
;
}
}
/* k i j p */
for
(
k=
1
;
k<=
n;
++
k)
{
for
(
i=
1
;
i<=
n;
++
i)
{
for
(
j=
1
;
j<=
n;
++
j)
{
if
(
a[
i]
[
j]
>
a[
i]
[
k]
+
a[
k]
[
j]
)
{
/* */
a[
i]
[
j]
=
a[
i]
[
k]
+
a[
k]
[
j]
;
/* */
path[
i]
[
j]
=
path[
i]
[
k]
;
}
}
}
}
}
/* */
int
isNegationLoop(
int
n)
{
int
i,j,k;
for
(
k=
1
;
k<=
n;
++
k)
{
for
(
i=
1
;
i<=
n;
++
i)
{
for
(
j=
1
;
j<=
n;
++
j)
{
/* k， i j ， */
if
(
a[
i]
[
j]
>
a[
i]
[
k]
+
a[
k]
[
j]
)
{
return
0
;
}
}
}
}
return
1
;
}
/* */
void
Print(
int
n)
{
int
i,j,next;
for
(
i=
1
;
i<=
n;
++
i)
{
for
(
j=
1
;
j<=
n;
++
j)
{
/*naxt path */
next=
path[
i]
[
j]
;
if
(
next==
-
1
)
{
printf
(
"%d - %d no path/n
"
,i,j)
;
}
else
{
/* i、j */
printf
(
"%d "
,a[
i]
[
j]
)
;
printf
(
"%d "
,i)
;
while
(
next!
=
j)
{
printf
(
"-> %d "
,next)
;
/* */
next=
path[
next]
[
j]
;
}
printf
(
"-> %d/n
"
,j)
;
}
}
}
}
int
main(
)
{
int
n,i,j,x,y,value;
scanf
(
"%d"
,&
n)
;
/* c*/
for
(
i=
0
;
i<=
n;
++
i)
{
for
(
j=
0
;
j<=
n;
++
j)
{
if
(
i==
j)
{
c[
i]
[
j]
=
0
;
}
else
{
c[
i]
[
j]
=
MAX;
}
}
}
while
(
1
)
{
/* */
scanf
(
"%d%d%d"
,&
x,&
y,&
value)
;
if
(
x==
0
&&
y==
0
&&
value==
0
)
{
break
;
}
c[
x]
[
y]
=
value;
}
Floyd(
n)
;
if
(
isNegationLoop(
n)
)
{
Print(
n)
;
}
else
{
printf
(
"the short loop isn't exit/n
"
)
;
}
system
(
"pause"
)
;
return
0
;
}