Floydアルゴリズム-すべての頂点間の最短パス(C++テンプレート)
15355 ワード
1
void
Floyd(
int
*
edge,
int
*
path,
const
int
order,
const
int
maxNum)
2
{
3
int
length;
4
if
(path
!=
NULL)
5
for
(
int
i
=
0
; i
<
order; i
++
)
6
for
(
int
j
=
0
; j
<
order; j
++
)
7
if
(i
!=
j
&&
(
*
(edge
+
order
*
i
+
j)
<
maxNum))
8
*
(path
+
order
*
i
+
j)
=
i;
9
else
10
*
(path
+
order
*
i
+
j)
=
0
;
11
12
for
(
int
k
=
0
; k
<
order; k
++
)
13
for
(
int
i
=
0
; i
<
order; i
++
)
14
for
(
int
j
=
0
; j
<
order; j
++
)
15
{
16
length
=
(
*
(edge
+
i
*
order
+
k)
+
*
(edge
+
k
*
order
+
j));
17
if
(length
<
*
(edge
+
i
*
order
+
j))
18
{
19
*
(edge
+
i
*
order
+
j)
=
length;
20
if
(path
!=
NULL)
21
*
(path
+
i
*
order
+
j)
=
*
(path
+
k
*
order
+
j);
22
}
23
}
24
}
呼び出し例:
1
cosnt
int
MaxNum
=
1000
;
2
int
a[
4
][
4
]
=
{{
0
,
1
, MaxNum,
4
}, {MaxNum,
0
,
9
,
2
}, {
3
,
5
,
0
,
8
}, {MaxNum, MaxNum,
6
,
0
}};
3
int
b[
4
][
4
];
4
Floyd((
int
*
)a, (
int
*
)b,
4
, MaxNum);