X Международная студенческая научная конференция Студенческий научный форум - 2018

В реальной жизни очень часто приходится решать задачу нахождения кратчайшего пути. Значимость данной задачи определяется её различными практическими применениями. Например, при составлении новых маршрутов (железные дороги, городской транспорт и др.).

Для решения данной задачи применима теория графов. В данных случаях качестве вершин выступают пункты назначения, а дороги являются ребрами, которые лежат между ними. Если сумма длин дорог между перекрестками минимальна, тогда найденный путь самый короткий.

Существует множество алгоритмов для решения данной задачи: Алгоритм Дейкстры, Алгоритм Беллмана — Форда, Алгоритм поиска A*, Алгоритм Флойда — Уоршелла, Алгоритм Джонсона Алгоритм Ли (волновой алгоритм) и др. Рассмотрим на конкретном примере работу наиболее известных алгоритмов. Представленные алгоритмы, для данного взвешенного графа позволяют найти кратчайшее расстояние от вершины , к вершине .

Найти кратчайшее расстояние от вершины , к вершине

Алгоритм Дейкстры. Опишем работу алгоритма:

Каждой вершине поставим в соответствие пару (: 0), где первая координата вершины (m, ) означает присвоенное расстояние от вершины , к вершине , а вторая координата показывает предыдущую вершину пути от к .

Начать в вершине (; 0) и заменить ее на (0;0), сделать ее постоянной. Остальные вершины оставить временными (как только вершина стала постоянной ее нельзя изменять).

Когда вершина (, ) станет постоянной, для каждой вершины смежной к прибавить величину m к расстоянию от вершины к вершине . Если это значение меньше чем текущее расстояние, присвоенное вершине , заменить текущее расстояние этой суммой и заменить вторую координату на .

Найти минимум из расстояний, приписанным вершинам. Первую из вершин таким расстоянием сделать постоянной.

Если - не постоянная вершина, то вернуться к пункту 2.

Если - постоянная вершина, то расстояние присвоенное вершине является кратчайшим расстоянием от к .

Для нахождения пути начать в вершине , найти предшествующую ей вершину пути, (по второй координате). Для каждой вершины пути находить предшествующую ей вершину пути, пока не будет достигнута вершина . Перестановка вершин в обратном порядке даст кратчайший путь.

Решение: Выполним действия, согласно алгоритму:

Каждой вершине поставим в соответствие пару (: 0),

По условию задачи начнем в вершине (; 0) и заменим ее на (0;0), сделаем постоянной (на рисунке обведем в кружок постоянные вершины).

Вершина стала постоянной, найдем вершины, смежные с ней. Это вершины , присваиваем им координаты (5;) и (6;)- это временные вершины, имеет наименьшее расстояние, делаем ее постоянной, т.е. получаем:

Рассмотрим временные вершины смежные с , найдем расстояние к временным вершинам.

: 5+7=12; : 5+10=15; 5+2=7 :5+3=8

Поскольку новое расстояние до =8 больше, чем уже присвоенное, то вершину оставляем без изменений и делаем постоянной.

Новые расстояния до , , меньше присвоенных.

Вершина стала постоянной, находим смежные с ней, выполнение шага 2 не приводит к изменениям, делаем вершину постоянной.

Найдем расстояние из в и используя шаг 2 меняем (15,) на (11,) таким образом, стала постоянной.

Для нахождения пути начнем в вершине , предшествующую ей вершину пути отыщем по второй координате, это вершина , из попадаем в , далее в . Перестановка вершин в обратном порядке даст кратчайший путь.

Получим: 11- кратчайшее расстояние от , к вершине кратчайший маршрут , . В графе кратчайший путь обозначен пунктирной линией.

Алгоритм Беллмана – Форда. Опишем работу алгоритма:

Пронумеровать все вершины графа, при этом вершина, из которой будут найдены кратчайшие пути во все остальные вершины, будет считаться первой (). Составим матрицу расстояний.

Около первой строки и над первым столбцом матрицы, поставить пометку «0», получим помеченную строку. В помеченной строке (слева направо), встречая клетку с числом, прибавить это число к пометке строки и сумму проставить над столбцом, в котором эта клетка находится. После просмотра первой строки отобразить пометки столбцов относительно главной диагонали. В новых помеченных строках вновь проделать же самое. Действие продолжается до тех пор, пока все строки и все столбцы не окажутся помеченными. При этом имеющуюся пометку менять нельзя.

Уменьшение пометок. Просмотреть клетки (слева направо ) и всякий раз, когда встречается число, сложить его с пометкой строки и сумма сравнить с пометкой столбца, в котором найденное число расположено. Если сумма оказалась меньше, чем пометка столбца, то эта пометка столбца меняется на полученную сумму. В противном случае, сумма остается прежней. Новые пометки столбцов отразить относительно главной диагонали и повторить процедуру. Действие продолжается до тех пор пока не будет ни каких изменений в пометках.

По пометкам построить кратчайшие пути из первой вершины во все остальные. Для этого зафиксировать вершину (например ). Длина искомого пути равна пометке, стоящей над столбцом. Предпоследняя вершина в кратчайшем пути из первой вершины в вершину находится следующим образом: в столбце номер n отыскиваем число, сумма которого с пометкой строки, в которой оно расположено, равна пометке, стоящей над столбцом. Номер строки, в которой найденное число оказалось, и будет предпоследней вершиной. Вершину, которая предшествует вершине данной, находим как предпоследнюю в кратчайшем пути и так далее.

Решение: Составим матрицу расстояний графа, для удобства данные запишем в виде таблицы:

		5				6
	5		7	10	2	3
		7		2
		10	2		4
		2		4		7
	6	3			7

Около первой строки и над первым столбцом матрицы, поставим пометку «0». В помеченной строке стоят цифры 5 и 6, прибавим их к пометке строки (к нулю) и сумму проставим над столбцом. Отобразим пометки столбцов относительно главной диагонали.

		0	5				6
	0		5				6
	5	5		7	10	2	3
			7		2
			10	2		4
			2		4		7
	6	6	3			7

Получим помеченные строки (с вершинами и . Расставим новые пометки, не изменяя при этом имеющиеся. Отразим относительно главной диагонали:

		0	5	12	15	7	6
	0		5				6
	5	5		7	10	2	3
	12		7		2
	15		10	2		4
	7		2		4		7
	6	6	3			7

Все пометки расставлены, переходим к уменьшению пометок. Проверим сумму числа с пометкой строки и сравним с пометкой столбца:

	0+5=5, 0+6=6 оставляем без изменений.
	5+5=10>0, 5+7=12, 5+10=15,5+2=7,5+3=8>6 оставляем без изменений.
	12+7=19>5, 12+2=140, 5+7=12, 5+10=15,5+2=7,5+3=8>6 оставляем без изменений.
	12+7=19>5, 12+2=14 оставляем без изменений.
	14+10>5, 14+2=16>12, 14+4=18>7 оставляем без изменений.
	7+2=9>5, 7+4=11

Код для цитирования: Скопировать