On Wed, Feb 26, 2003 at 09:45:06AM +0100, Alfredo Braunstein wrote:
> Andre Poenitz wrote:
>
> > I think I have some code flying around that implement shortest path
> > searches. Interested?
>
> Absolutely, but:
>
> If you think it's ok, I would try to make the separation first without
> changing the existing code.
Sure.
> Once I have this working, we can think of
> changing the graph code (we can even consider putting boost.graph if we
> feel greedy).
Nah. Overkill.
> Send it anyway if you have it at hand.
Just a snippet ("ebert" is my graph structure, the rest is hopefully
self-explanatory), array<> could be replaced by map<>, and node and edge
by int....
typedef array<node, edge> pathset;
pathset shortest_paths(const ebert & G, node u, const weights & W)
{
const double infin = 1e30;
nodeset U; // seen nodes
U += u;
array<node, edge> p(nbegin(G), nend(G), edge(0)); // previous edges
array<node, double> h(nbegin(G), nend(G), infin); // costs
h[u] = 0;
array<node, double> g;
foreach_incident_edge(e, u, G) {
node j = second_node(G, e);
h[j] = W(e) + W(j);
p[j] = e;
}
while (1) {
node v; // next unseen node with minimum weight
double minimum = infin;
foreach_node(w, G) {
if (U(w) || h(w) > minimum)
continue;
minimum = h(w);
v = w;
}
U += v;
g[v] = h(v);
if (U.card() == node_count(G))
break;
// from now on plain Dijkstra
foreach_incident_edge(e, v, G) {
node j = second_node(G, e);
if (U(j))
continue;
double c = g(v) + W(e) + W(j);
if (c >= h(j))
continue;
h[j] = c;
p[j] = e;
}
}
return p;
}
path shortest_path(const ebert & G, const dpair & q, const weights & cost)
{
return build_path(G, q, shortest_paths(G, q.first, cost));
}
path build_path(const ebert & G, const dpair & q, pathset prev)
{
path p;
if (!prev(q.second).id())
return p;
for (node w = q.second, t; w != q.first; w = t) {
t = opposite(G, prev(w), w);
p.push_back(prev(w), w, t);
}
p.reverse();
return p;
}
path shortest_path(const ebert & G, const dpair & p)
{
return shortest_path(G, p, default_weights(G));
}
--
Those who desire to give up Freedom in order to gain Security,
will not have, nor do they deserve, either one. (T. Jefferson)
