Вот алгоритм
INPUT: G = (V, E), s, t
n = |V|
ARRAY: OPT[0..n, V]
FOREACH v V
OPT[0, v] =
OPT[0,s] = 0
FOR i = 1 to n
FOREACH v V
m = OPT[i-1, v]
m' =
FOREACH (u, v) E
m' = min (m', OPT[i-1, u] + c[u,v])
OPT[i, v] = min(m, m')
RETURN OPT[n-1, t]
А вот мой метод
Код: Выделить всё
public boolean FindShortestPath()
{
int m=0;
int mTag=0;
for (int i=0;i<graph.returnNumOfVertic();i++)
OPT[0][i]=BIG_NUMBER; //equals infinity
OPT[0][0]=0;
for (int vertexIndex=1;vertexIndex<graph.returnNumOfVertic();vertexIndex++)
{
for (int v = 0; v < graph.returnNumOfVertic(); v++)
{
AdjList A = graph.getAdjList(v);
m=OPT[vertexIndex-1][v];
mTag=BIG_NUMBER;
for (Edge edge = A.begEdge(); !A.end(); edge = A.nxtEdge())
{
int x=OPT[vertexIndex-1][edge.getV()];
int y=edge.getWeight();
mTag = Math.min(mTag, (x + y) );
}
int min=Math.min(m,mTag);
OPT[vertexIndex][v]=min;
}
}
return true;
}
