2 #include "distfunc.h"
\r
4 const float INFINITY = float(1e29);
\r
5 const unsigned NILL = uInsane;
\r
7 static float *ShortestPathEstimate;
\r
8 static unsigned *Predecessor;
\r
10 static void GetMostDistantPair(DistFunc &DF, unsigned *ptrIndex1, unsigned *ptrIndex2)
\r
12 const unsigned uNodeCount = DF.GetCount();
\r
14 Quit("GetMostDistantPair: < 2 seqs");
\r
16 float MaxDist = -1;
\r
17 unsigned Index1 = uInsane;
\r
18 unsigned Index2 = uInsane;
\r
19 for (unsigned i = 0; i < uNodeCount; ++i)
\r
21 for (unsigned j = i + 1; j < uNodeCount; ++j)
\r
23 float d = DF.GetDist(i, j);
\r
33 assert(Index1 != uInsane);
\r
34 assert(Index2 != uInsane);
\r
36 *ptrIndex1 = Index1;
\r
37 *ptrIndex2 = Index2;
\r
40 static void InitializeSingleSource(DistFunc &DF, unsigned uIndex)
\r
42 const unsigned uNodeCount = 0;
\r
44 for (unsigned i = 0; i < uNodeCount; ++i)
\r
46 ShortestPathEstimate[i] = INFINITY;
\r
47 Predecessor[i] = NILL;
\r
49 ShortestPathEstimate[uIndex] = 0;
\r
52 static void Relax(DistFunc &DF, unsigned u, unsigned v)
\r
54 float w = DF.GetDist(u, v);
\r
55 float d = ShortestPathEstimate[u] + w;
\r
56 if (ShortestPathEstimate[v] > d)
\r
58 ShortestPathEstimate[v] = d;
\r
63 void ShortestPath(DistFunc &DF, unsigned uIndex)
\r