WikiSort.ru - Программирование

Примеры

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

Вариант 2. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула.

Формальное определение

Дан взвешенный ориентированный^[1] граф ${\displaystyle G(V,E)}$ без петель. Найти кратчайшие пути от некоторой вершины ${\displaystyle a}$ графа ${\displaystyle G}$ до всех остальных вершин этого графа.

Обозначения

• ${\displaystyle N}$  — множество вершин графа
• ${\displaystyle M}$  — множество ребер графа
• ${\displaystyle g[ij]}$  — вес (длина) ребра ${\displaystyle ij}$
• ${\displaystyle s}$  — вершина, расстояния от которой ищутся, то есть стартовая вершина.
• ${\displaystyle d[i]}$  — это текущая длина кратчайшего пути от вершины ${\displaystyle s}$ до вершины ${\displaystyle i}$
• ${\displaystyle p[i]}$  — это вершина, предшествующая вершине ${\displaystyle i}$ в кратчайшем пути от вершины ${\displaystyle s}$ до ${\displaystyle i}$ .
• ${\displaystyle M0}$  — вершины, расстояние до которых уже вычислено (но, возможно, не окончательно);
• ${\displaystyle M1}$  — вершины, расстояние до которых вычисляется;
• ${\displaystyle M2}$  — вершины, расстояние до которых ещё не вычислено.
• ${\displaystyle state[i]}$  — хранит номер множества, к которому относится вершина i.

Код

Сразу стоит оговорить тот факт, что приведённый ниже код является не вполне работоспособным, так как не задана (каким-либо образом) структура графа. В итоге (по умолчанию) складывается ситуация, при которой имеется граф, состоящий из десяти (значение по умолчанию) изолированных вершин, а кратчайший путь ищется от вершины с индексом 1 до вершины с индексом 3 (значения по умолчанию).

#include <iostream>
// для структуры pair:
#include <utility>
#include <vector>
#include <deque>
// для значения INT_MAX:
#include <climits>
// для функции reverse:
#include <algorithm>

using namespace std;

typedef pair<int,int> rib;
typedef vector < vector<rib> > graph;

const int INFINITY = INT_MAX;

// Значения по умолчанию для работы алгоритма (число вершин графа, индексы начальной и конечной вершин пути)
int defaultNumber = 10, 
    defaultStart = 1, 
    defaultFinish = 3;

int main()
{
    int numberOfVertices = defaultNumber,  
        startVertex = defaultStart, 
	finishVertex = defaultFinish;

    graph g (numberOfVertices);
    
	// Здесь считываем структуру графа (откуда-либо, например, из файла).
	// К слову, размерность и номера вершин для поиска скорее всего
	// необходимо получать из того же источника.

    vector<int> d (numberOfVertices, INFINITY);
    d[startVertex] = 0;
    
    vector<int> state (numberOfVertices, 2);
    state[startVertex] = 1;
    
    deque<int> q;
    q.push_back (startVertex);
    
    vector<int> p (numberOfVertices, -1);

    while (!q.empty())
    {
        int vertex = q.front();  
        q.pop_front();
        state[vertex] = 0;
        for (size_t i = 0; i < g[vertex].size(); ++i)
        {
            int to = g[vertex][i].first, 
                length = g[vertex][i].second;
            if (d[to] > d[vertex] + length)
            {
                d[to] = d[vertex] + length;
                if (state[to] == 2)
                    q.push_back (to);
                else if (state[to] == 0)
                    q.push_front (to);
                p[to] = vertex;
                state[to] = 1;
            }
        }
    }
    if (p[finishVertex] == -1)
    {
        cout << "No solution" << endl;
    }
    else
    {
        vector<int> path;
        for (int vertex = finishVertex; vertex != -1; vertex = p[vertex])
            path.push_back (vertex);
        reverse (path.begin(), path.end());
        for (size_t i = 0; i < path.size(); ++i)
            cout << path[i] + 1 << ' ';
    }

    // для запуска не из командной строки (чтобы была возможность увидеть результат)
    cin.get();
    return 0;
}

Описание

Пусть массив D[1..N] будет содержать текущие кратчайшие длины путей. Изначально массив D заполнен значениями «бесконечность», кроме D[s] = 0. По окончании работы алгоритма этот массив будет содержать окончательные кратчайшие расстояния.

Пусть массив P[1..N] содержит текущих предков. Так же как и массив D, массив P изменяется постепенно по ходу алгоритма и к концу его принимает окончательные значения.

Изначально все вершины помещаются в множество M2, кроме вершины V0, которая помещается в множество M1.

На каждом шаге алгоритма мы берём вершину из множества M1 (достаём верхний элемент из очереди). Пусть V — это выбранная вершина. Переводим эту вершину во множество M0. Затем просматриваем все рёбра, выходящие из этой вершины. Пусть T — это второй конец текущего ребра (то есть не равный V), а L — это длина текущего ребра.

• Если T принадлежит M2, то T переносим во множество M1 в конец очереди. DT полагаем равным DV + L.
• Если T принадлежит M1, то пытаемся улучшить значение DT: DT = min (DT, DV + L). Сама вершина T никак не передвигается в очереди.
• Если T принадлежит M0, и если DT можно улучшить (DT > DV + L), то улучшаем DT, а вершину T возвращаем в множество M1, помещая её в начало очереди.

Разумеется, при каждом обновлении массива D следует обновлять и значение в массиве P.

Сложность алгоритма

При неправильной реализации алгоритма, используя вместо очередей M1' и M1'' дек и добавляя вершины из M0 в начало дека, алгоритм в худшем случае будет работать за экспоненциальное время^[2], так делать не рекомендуется. На реальных графах алгоритм зарекомендовал себя достаточно хорошо: время его работы ${\displaystyle O(MN)}$ ^[3].