һ
.
( )
2
:
:
:
-. -71
.
:
..
2012
, , . .
G = (X, U) S = (0, 1), (x1, 2),..., ((l-I), x(l)), (), (l) - . , G . S . q R G q- .
, R G
 |
1
. , , .
:
, 0 = 1, .
, , , , . G
S1 = (x1, 2), (2, 3), (3, 4),(4,1),(1,2) -
S2 = (1, 2), (2, 3), (3, 4), (4, 1)
 |
2
S3= (1,2)(2,3)(3,4)
S4= (1,2)(2,4)(4,5)(5,3)(3,2)(2,4) .
3 .
. .
|
|
|
.
1) R G
xk V(k) = 0, V(n) = M.
2) 1 xi.
V(j) > V(i) + rij. V(j) V(i) + rij.
3) 1,2 .
4) .
.
#include <iostream>
using namespace std;
int main()
{
const int n = 9;
int m[n][n] = { {0,3,0,6,0,0,0,7,3},
{3,0,5,0,0,0,0,9,11},
{0,5,0,8,6,0,0,0,12},
{6,0,8,0,3,0,14,10,5},
{0,0,6,3,0,2,4,6,0},
{0,0,0,0,2,0,15,13,0},
{0,0,0,14,4,15,0,1,0},
{7,9,0,10,6,13,1,0,3},
{3,11,12,5,0,0,0,3,0}};
int V[n],xk,cache;
xk = m[0][0];
for(int j = 0; j < n; j++)
{
if(j == 0)
V[j] = xk;
else
V[j] = -1;
}
for(int i = 0; i < n; i++)
{
for(int j =i; j < n; j++)
{
if(m[i][j]!= 0)
{
if(V[j] == -1)
{
V[j] = V[i] + m[i][j];
}
else
if(V[j] < V[i] + m[i][j])
break;
else
V[j] = V[i] + m[i][j];
/*else
if(cache < V[j])
V[j] = V[i] + m[i][j];
else
V[j] = m[i][j];*/
}
}
}
for(int i =0; i < n; i++)
cout << V[i] << " ";
return 0;
}
. . .
.
1. l(s) = 0, l(xi) = -1 xi!= s .
2. l(xi) <- min[l(xi); l(p) + r(p,xi)] .
3. , l(xi) = min[l(xi)]/
4. xi p = xi.
