Основы программирования. Пути на графах

Поиск кратчайших путей в графе

Алгоритм Дейкстры

Алгоритм Дейкстры

Алгоритм Дейкстры

Алгоритм Дейкстры

Алгоритм Дейкстры

Методы WGraph для алгоритма Дейкстры
void WGraph::minpath(int s, double *D, 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 до всех остальных
Матрица расстояний в общем случае несимметричная
s=0
+ вершина 3:
D
+ вершина 2:
D
+ вершина 1:
D

Вычисление кратчайших расстояний от вершины s до всех остальных
Матрица расстояний:
s=0
Кратчайшие расстояния от вершины 0:
D
Кратчайшие пути от вершины 0 в обратном порядке:
P

Алгоритм Флойда-Уоршалла

Алгоритм Флойда-Уоршалла

Алгоритм Флойда-Уоршалла

Алгоритм Флойда-Уоршалла
Вычисляется матрица весов всех кратчайших путей.
double** WGraph::allminpath()
{ int 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).

Вставка побочного цикла в текущий

Вставка списка в список
Вставка списка 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;
}

Вспомогательные методы
Выделение произвольного пути из a в b (a=b в случае цикла) с исключением просмотренных ребер. Путь формируется в виде списка пройденных вершин 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;
}
}