Table 'system_articles_sessions' is marked as crashed and should be repaired АЛГОРИТМЫ НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ - X Студенческий научный форум - 2018
     
 
X Международная студенческая научная конференция
«Студенческий научный форум» - 2018
 
     

АЛГОРИТМЫ НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ
Бережнова К.М.
Текст научной работы размещён без изображений и формул.
Полная версия научной работы доступна в формате PDF


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  3. По пометкам построить кратчайшие пути из первой вершины во все остальные. Для этого зафиксировать вершину (например ). Длина искомого пути равна пометке, стоящей над столбцом. Предпоследняя вершина в кратчайшем пути из первой вершины в вершину находится следующим образом: в столбце номер 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