Основы программирования

int *P)
{ int i, j, w; double wmin;
bool *old

= new bool[vernum];
for (i = 0; i < vernum; i++)
{ old[i] = false; D[i] = mat[s][i]; P[i]=s; }
old[s] = true; D[s] = 0;
for (i = 1; i < vernum; i++) {
for (w=-1, wmin=MAX, j=0; j if (!old[j] && D[j] < wmin)
{ w = j; wmin = D[j]; }
if (w < 0) break;
for (old[w] = true, j = 0; j < vernum; j++)
if (!old[j] && D[j] > D[w]+mat[w][j])
{ D[j] = D[w]+mat[w][j]; P[j] = w; }
} delete [] old;
}

в общем случае несимметричная
s=0





+ вершина 3:

D
+ вершина 2:
D
+ вершина 1:
D

расстояния от вершины 0:

D
Кратчайшие пути от вершины 0 в обратном порядке:

P

i, j, l;
double **W = new double* [vernum];
for

(i = 0; i < vernum; i++)
W[i] = new double[vernum];
for (i = 0; i < vernum; i++)
for (j = 0; j < vernum; j++)
W[i][j] = mat[i][[j];
for (l = 0; l < vernum; l++)
for (i = 0; i < vernum; i++) {
if (W[i][l] < MAX)
for (j = 0; j < vernum; j++)
W[i][j]=min(W[i][j], W[i][l]+W[l][j]);
return W;
}

при которых применимо ДП:
оптимизационная задача, для которой выполняется свойство оптимальности

для подзадач;
относительно небольшое (полиномиальное от длины входа) число различных подзадач;
многократное решение одних и тех же подзадач при поиске общего решения на основе полного перебора вариантов – перекрывающиеся подзадачи.

структуру оптимальных решений задачи и подзадач;
найти рекуррентное соотношение, связывающее оптимальные

параметры\решения подзадач разных уровней;
двигаясь снизу вверх, от подзадач самого низкого уровня, вычислять их оптимальные параметры\решения только один раз и сохранять результаты в специальной таблице;
использовать данные из таблицы при поиске оптимального параметра\решения подзадач следующего уровня.
В приведенном алгоритме allminpath оптимальные решения подзадач разных уровней последовательно вычисляются в матрице W.

вершине a
проходит по всем ребрам графа по одному разу
завершается в

вершине a.
Условия существования эйлерова цикла:
граф является связным
степени всех вершин графа (число инцидентных ребер) четные (т.е. если существует ребро, по которому можно прийти в вершину, то всегда найдется ребро, по которому можно выйти).
Если в графе существуют ровно 2 вершины a и b с нечетными степенями, то можно найти эйлеров путь, который начинается в a, проходит по всем ребрам по одному разу и заканчивается в b.

цикла/пути не выполняются, то выход.
Выбирается произвольная вершина a (для цикла)

или выделяются 2 вершины с нечетными степенями a и b (для пути).
Строится произвольный начальный (текущий) цикл из a или путь из a в b.
Для всех вершин v текущего цикла/пути (начиная с v=a) проверяется, есть ли еще не пройденные ребра, инцидентные v. Если есть, то выделяется побочный цикл, который начинается и заканчивается в v и проходит по не проверенным ранее ребрам. Далее побочный цикл включается в текущий непосредственно за вершиной v.

виде списков. Используем для этого класс List из раздела «Линейные

списки». Элементы списков будут хранить номера пройденных вершин.
Для представления графа используем класс LGraph (списки смежных вершин).
Для исключения пройденных ребер можно просто удалять элементы в списках смежных вершин. Чтобы сохранить исходный массив списков lst, следует создать и модифицировать его копию, но для упрощения алгоритма мы используем сам lst.
Для вставки побочного цикла в текущий (вставки списка в список с заданной позиции) добавим в класс List новый метод insert(List &sec).

позиция pcurpos не изменяется):
bool List::insert(List &sec)
{
if (!pcurpos ||

sec.is_empty())
return false;
(sec.pend)->next = pcurpos->next;
if (pcurpos == pend) pend = sec.pend;
pcurpos->next = sec.pbeg;
sec.pend = sec.pbeg = NULL;
return true;
}
bool List::is_empty()
{ return (!pbeg)? true : false; }

вершины (a и b, для цикла a=b=0).
bool LGraph::is_euler_path(int &a,

int &b)
{ int i, k = 0;
for (i = 0; i < vernum; i++)
if (lst[i].getcount() % 2 == 1)
{ k++;
if (k == 1) a = i;
else if (k == 2) b = i;
else return false;
}
if (!k) a = b = 0;
return true;
}

случае цикла) с исключением просмотренных ребер. Путь формируется в виде

списка пройденных вершин path.
void LGraph::get_path(int a, int b, List &path)
{ int i, vpre = a, vnex;
path.clear(); path.push_back(a);
while (true)
{
vnex = lst[vpre].pop_front();
lst[vnex].remove(vpre);
path.push_back(vnex);
if (vnex == b) break;
vpre = vnex;
}
}

List curpath, secpath; int beg, end, *pver;
if (!is_euler_path(beg,

end)) return curpath;
get_path(beg, end, curpath);
pver = curpath.get_first();
while (true)
{ if (lst[*pver].is_empty())
{ pver = curpath.get_next();
if (pver == NULL) return curpath;
continue;
}
get_path(*pver, *pver, secpath);
secpath.pop_front();
curpath.insert(secpath);
}
}