Дистанционные семинары

Матрица смежности полученного графа будет очень большой. Заметим, что для любой вершины мы можем без труда найти всех ее соседей. Представим себе, что шахматная доска бесконечна во все стороны. Тогда для любой клетки (x,y) существует ровно восемь соседей: (x+2,y+1), (x+2,y-1), (x+1,y+2), (x+1,y-2), (x-1,y+2), (x-1,y-2), (x-2,y+1), (x-2,y+1). Нашу конечную шахматную доску можно представить как часть бесконечной, и при вычислении соседей просто проверять, попадает ли клетка в рамки нашей доски или нет.

Мысленно сотрем из записи координат соседей данной клетки x и y. Получим: (+2,+1), (+2,-1), (+1,+2), (+1,-2), (-1,+2), (-1,-2), (-2,+1), (-2,-1). Эти числа показывают смещения координат клеток, соответствующих соседним вершинам, относительно координат клетки, соседей которой нам необходимо найти. Если записать эти смещения в два массива: первый - смещение по x, второй - соответсвующее ему смещение по y, то перебор всех соседей клетки сведется к циклу от 1 до 8:

const
  dx: array [1..8] of integer = (2, 2, 1, 1,-1,-1,-2,-2);
  dy: array [1..8] of integer = (1,-1, 2,-2, 2,-2, 1,-1);
  {...}
  for i := 1 to 8 do
  begin
    newx:=x+dx[i];
    newy:=y+dy[i];
    {...}
  end

Таким образом, в этой задаче граф вообще не нужно хранить в памяти компьютера. Заметим, что обход этого графа в ширину будет занимать порядка N*N действий, т.е. пропорционально количеству вершин в нем. Дело в том, что на каждом шаге мы рассматриваем не все вершины, а только соседей, которых не более 8.

Задача 05-3. Табличка

Как и в предыдущей задаче, граф не нужно хранить в памяти компьютера

Обозначим начальную вершину X.

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

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

На каждом шаге мы будем совершать следующие действия:

• 
  Найдем минимум из расстояний от начальной вершины до вершин из второго множества и запомним вершину второго множества, на которой этот минимум достигается (обозначим ее Р)
  
• 
  Перенесем вершину Р из второго множества в первое
  
• 
  Переберем всех соседей вершины Р. Обозначим текущего соседа, с которым мы работаем, U. Заметим, что в данный момент мы нашли путь из вершины Х в вершину U: это путь из вершины Х в вершину Р, дополненный ребром (Р,U).
  
  1. 
     Если U лежит в третьем множестве, то мы должны перенести вершину U во второе множество, а расстояние до него посчитать как длину пути, описанного выше.
     
  2. 
     Если U лежит во втором множестве, то сравнив длину нового найденного нами пути и ранее известное расстояние до этой вершины, запишем вместо ранее известного расстояния минимальное из них
     
  3. 
     Если сосед U лежит в первом множестве, то с ним нам делать ничего не нужно, ведь до него наилучшее расстояние уже найдено, и с помощью любых дополнительных проверок улучшить его не удастся.
     

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

Хранить множества лучше всего с помощью массива из N элементов, где соответствующий элемент равен 0, если вершина лежит в первом множестве, 1 - если во втором и 2 - если в третьем .

Восстановление пути
Заметим, что если кратчайший путь до вершины v проходит через вершину u, то часть этого пути до вершины u является кратчайшим путем до вершины u. Значит, чтобы сохранить путь до всех вершин достаточно для каждой вершины хранить предыдущую в кратчайшем пути до нее.
Задача 06-1. Разминка

Задача 06-2. Алгоритм Дейкстры

Задача 06-3. Заправки

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

Задача 06-4. Автобусы

Марие Ивановне требуется добраться из деревни d в деревню v как можно быстрее (считается, что в момент времени 0 она находится в деревне d).

Пусть дан взвешенный граф с N вершинами и M ребрами. Требуется найти кратчайшие расстояния между всеми парами. Эта задача может быть решена с помощью алгоритма Флойда.

Рассмотрим два случая:

I. В графе нет циклов отрицательного веса.

В основе алгоритма Флойда лежит метод динамического программирования. Пусть A^k - матрица размера NxN с элементами a^k_i,j, где a^k_i,j - длина кратчайшего пути между вершинами i и j, проходящего через вершины с номерами меньше либо равными k (не считая начальной и конечной вершин). Тогда A⁰ - матрица смежности нашего графа, Aⁿ - искомая матрица кратчайших расстояний. Найдем a^k_i,j, зная A^k-1. Заметим, что в кратчайшем пути между вершинами i и j, содержащем вершины с номерами от 1 до k (т.е. соответсвующем a^k_i,j) вершина k может либо встречаться, либо нет. Значит a^k_i,j = min(a^k-1_i,j , a^k-1_i,k + a^k-1_k,j).

Один из вариантов реализации алгоритма Флойда выглядит так:
   for k := 1 to n do
     for i := 1 to n do
       for j := 1 to n do
         if a[k,i,j] > a[k-1,i,k] + a[k-1,k,j] then
           a[k,i,j] := a[k-1,i,k] + a[k-1,k,j];

Пусть у нас есть кратчайший путь из вершины i в вершину k. Заметим тогда, что в этом пути вершина k не может встречаться среди промежуточных вершин. Действительно, пусть это не так, тогда в нашем графе найдется цикл отрицательного веса, а этого по условию быть не может. В наших обозначениях это выглядит так: a[k,i,k]=a[k-1,i,k] и a[k,k,j]=a[k-1,k,j] для любых i и j. Значит алгоритм Флойда можно изменить следующим образом:

В этом случае между некоторыми парами вершин может быть сколь угодно короткий путь. Найи такие пары несложно по матрице "кратчайших" путей, посторенных алгоритмом Флойда. Имеют место утверждения:

1. 
   Если существует цикл отрицательного веса, проходящий через вершину i, то a_i,i будет меньше 0.
   
2. 
   Между парой вершин (i,j) существует сколь угодно малый путь тогда и только тогда, когда существует путь из i в j, содержащий цикл отрицательного веса или, иными словами, существует вершина k такая, что существует путь из i в k, из k в j и существует цикл отрицательного веса, проходящий через k
   

Задача 07-1. Флойд – 1

Задача 07-2. Флойд