Алгоритм Левита
Необходимо найти кратчайшие расстояния в графе от заданной вершины до всех остальных
В реализации необходимо использовать двунаправленную очередь, рекомендую писать её самому, а не использовать deque < int >, тогда выйгрыш во времени будет существенный.
Асимптотика O(NM).
На практике алгоритм работает гораздо быстрее, приближаясь к O(M).
Листинг C++
const int inf = (int)1e9;
class edge
{
public :
int v, w;
edge (int _v = 0, int _w = 0) : v (_v), w (_w) {};
};
void levit (int x, vector < vector < edge > > &e,
vector < int > &w, vector < int > &p)
{
int i, j;
int n = e.size ();
w.assign (n, inf);
p.assign (n, - 1);
w[x] = 0;
vector < int > id (n, 2);
deque < int > m1;
id[x] = 1;
m1.push_back (x);
while (m1.size ())
{
int v = m1.front ();
m1.pop_front ();
id[v] = 0;
for (i = 0; i < e[v].size (); ++ i)
{
int to = e[v][i].v;
int l = e[v][i].w;
if (id[to] == 2)
{
id[to] = 1;
m1.push_back (to);
}
if (id[to] == 0 && w[to] > w[v] + l)
{
id[to] = 1;
m1.push_front (to);
}
if (w[to] > w[v] + l)
{
w[to] = w[v] + l;
p[to] = v;
}
}
}
}
19.05.2007, 14:50
По всем вопросам обращаться: rumterg@gmail.com