Алгоритм Дейкстры. Реализация на очереди С++.

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

1. INITIALIZE_SINGLE_SOURCE(G,S)
2. S=0
3. Q=V[s] //добавляем стартовую вершину в очередь с приоритетом
4. While(!Q.empty()) //пока очередь не пуста
1. u=Extract_Min(Q) //берем вершину из очереди с минимальным расстоянием
2. for v из Adj[u] //для любой смежной вершины v к u
1. Relax (u,v,w) //производим релаксацию ребра

Процесс релаксации описан в алгоритме Форда-Беллмана:

Форд-Беллман

Реализация:

 
void Dijkstra_Shortest_Path(unsigned NumOfVertices, unsigned start){
int M [5][5] = {{0,6,0,7,0}, {0,0,5,8,-4}, {0,-2,0,0,0},{0,0,-3,0,9},{2,0,7,0,0}};
priority_queue< pair< unsigned int,double>, vector< pair > , Prioritize > Q;    
    int u,v,w;
    vector< double> d(NumOfVertices,INFINITY);
    d[start] = 0;
    Q.push(pair< unsigned int,double >(start,d[start]));
    while(!Q.empty())
    {
        u = Q.top().first;
    final.push(u);
        Q.pop();
        for(int v = 0 ; v < NumOfVertices ; v++)
        {
   if (M[u][v]) {
            w = M[u][v];
            cout< d[u] + w)
            {
                d[v] = d[u] + w;
                Q.push(pair(v,d[v]));
            }
   }
        }
    }
    for(int i=0; i< NumOfVertices; i++) 
   cout< <"Vertex "< < i< <" cost of vertex: "< < d[i]< < endl;
}

Для того, чтобы добавление в очередь с приоритетом работало, то есть сортировалось в процессе добавления пары, нужно сделать класс-компаратор и перегрузить оператор <

 
class Prioritize
{
public:
    int operator() ( const pair& p1, const pair& p2 )
    {
        return p1.second < p2.second;
    }
};

Read More

Топологическая сортировка+Поиск кратчайшего пути

Топологическая сортировка - линейное упорядочивание всех его вершин. Предположим, что граф не содержит циклов, так как если он содержит циклы, то такая сортировка не возможна.

Граф, который не содержит циклов, называется ациклическим.

Ориентированные ациклические графы используются для указания последовательности действия, где каждое действие зависит от других. Например: установка программ с помощью системы управления пакетами или сборка с помощью Makefil'ов. (wikipedie (c))

Топологическая сортировка проводится с помощью поиска в глубину, которая описана в моем блоге: Поиск в глубину
Суть топологической сортировки можно связать с временем закрытия. Чем больше время закрытия, тем первее будет вершина графа в сортировке.
Пример отсортированного графа:

На рисунке представлена последовательность одевания утром. Первым делом идут носки (socks), потом трусы (undershorts) и самым последним идет пиджак у него время закрытия 4.

Для реализации топологической сортировки нам всего лишь нужно добавить в реализацию поиска в глубину глобальный стэк для вершин - stack<unsigned int> answer;
И! где мы красим вершину в черный после цикла, добавим добавление вершины в стек:

answer.push(u);

Теперь нам осталось всего лишь вывести стек) Вот и получили ответ.

Приложение: поиск кратчайшего пути в ациклическом графе.
Алгоритм выглядит так:

1. Сначала делаем топологическую сортировку графа
2. Для каждой вершины u в порядке топологической сортировки
1. Для каждой смежной вершине v к вершине u
1. Делаем релаксацию, т.е. запускаем старую добрую RELAX(u,v,w) 

Read More

Поиск в глубину у графа

Поиск в глубину - это метод прохода графа, когда просматривается еще не пройденная вершина, потом происходит проход по смежным вершинам, затем когда остаются не иследованные ребра, происходит возврат в вершину. Алгоритм работает до тех пор, пока не будут открытые все вершины, достижимые из исходной.
Сам алгоритм:
Он состоит из 2 ух процедур:

1. DFS(G) - нужна для инициализации всех переменных и цикла для прохода по всем вершинам
2. DFS_VISIT(u) - где u - вершина, которую нужно посетить. Эта процедура обработки вершина, где проиходит окраска каждой вершины, обозначения времени открытия и закрытия вершины (закрытие - окраска в черный цвет, открытие - окраска в серый цвет).

DFS(G)

Для каждой вершины u из множества вершин Графа

Окрасить в белый цвет

Инициализировать счетчик времени нулем
Для каждой вершины u из множества вершин Графа

Если вершина окрашена в белый, т.е. не пройдена

Посетить ее, т.е. запустить процедуру DFS_VISIT(u)

DFS_VISIT(u)

Окрасить вершину в серый цвет
Увеличить счетчик времени time++
Обозначить время открытия d[u]=time
Для каждой вершины v смежной нашей вершине u

Если вершина v окрашена в белый, т.е. не пройдена

Обозначить u как вершину предшествующую вершине v
Рекурсивно вызвать процедуру обработки для v: DFS_VISIT(v)


Окрасить вершину u в черный цвет
Обозначить время закрытия f[u]=time=time+1

Использующиеся данные:

Глобальная область видимости:

vector<unsigned int> color; //вектор цветов, 0 - белый, 1 - серый, 2 - черный

vector<unsigned int> predcessors; //вектор предшественников, если хотите построить дерево глубины

vector<unsigned int> d; //вектор к-ый хранит время открытия вершины

vector<unsigned int> f;  //вектор к-ый хранит время закрытия вершины

unsigned int timer; //таймер

ConnectionMatrix-матрица смежности графа

Реализация процедуры DFS:

void DFS (unsigned int NumOfVertices, double **ConnectionMatrix){

color.assign(NumOfVertices,0); //инициализация всех векторов

predcessors.resize(NumOfVertices);

d.resize(NumOfVertices);

f.resize(NumOfVertices);

timer=0; //обнуляем таймер

for (int u=0; u<NumOfVertices; u++){

if (color[u]==0) //если не пройденна - посетить

DFS_VISIT(u, ConnectionMatrix, NumOfVertices);

}

}

Реализация DFS_VISIT:

void DFS_VISIT(unsigned int u, double **ConnectionMatrix, unsigned int NumOfVertices){

color[u]=1; //теперь вершина окрашена в серый

timer++; //увеличим время

d[u]=timer; //время открытия

for (unsigned int v=0; v<NumOfVertices; v++){

if (ConnectionMatrix[u][v])

if (color[v]==0){

predcessors[v]=u;

DFS_VISIT(v, ConnectionMatrix, NumOfVertices); //рекурсивынй вызов для                       вершины v

}

}

color[u]=2; //покрасим в черный

f[u]=timer=timer+1; //обозначим время закрытия вершины u

}

Read More

Поиск в ширину у графа

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

• Суть данного алгоритма в том, что в процессе обхода мы идем вширь, то есть, перед тем, как приступить к поиску вершин на расстоянии k+1, мы выполняем обход всех вершин на расстоянии k.
• Для отслеживания процесса обхода, мы окрашиваем вершины в белый, серый или черный цвета.
• Сначала мы все вершины у нас белые, начальную вершину мы красим серым цветом, для обозначения окраса у нас есть вектор colors[numOfVertices]:
1. color[i]=0 - белый цвет
2. color[i]=1 - серый цвет
3. color[i]=2 - черный цвет
• Еще у нас есть вектор расстояний d[numOfVertices] - очень удобная штука, чтобы посмотреть, есть ли у нас какие нибудь несвязные вершины.

Алгоритм:

1. Пока очередь не пуста:
1. Взять первый элемент из очереди u
2. Цикл для каждой связной с вершиной u вершиной (v)
1. если у нас вершина v не окрашенная
1. окрасит в серый
2. пометить в векторе, что d[v]=d[u]+1
3. добавить вершину в очередь
3. Окрасить вершину u в черный цвет

Реализация:

void BFS(unsigned int NumOfVertices, double **ConnectionMatrix, unsigned int start, unsigned int target){
  //BFS algorithm
 if (target==start) return;
 const double INFINITY=1E10;
 unsigned int u=start;
 //0-white, grey-1, black-2
 vector  d (NumOfVertices,INFINITY); //вектор расстояний
 d[start]=0;
 vector  color(NumOfVertices,0); //вектор закраски
 color[start]=1;
 vector  predcessors (NumOfVertices);
 predcessors[start]=-1;
 queue  q;
 q.push(start);
 while (!q.empty()) {
  u=q.front();
  q.pop();
  for (int v=0; v< NumOfVertices; v++) {
   if (color[v]==0&&ConnectionMatrix[u][v]) {
    color[v]=1;
    d[v]=d[u]+1;
    predcessors[v]=u;
    q.push(v);
   }
  }
  color[start]=2;
 }
 cout< path;
 for (int cur=target; cur!=-1; cur=predcessors[cur])
  path.push_back (cur);
 reverse (path.begin(), path.end());
 cout << "Path from " << start << " to " << target << ": ";
 for (size_t i=0; i

Read More

Алгоритм Форда-Беллмана. Реализация на С++

Алгоритм Форда-Беллмана применяется для нахождения кратчайшего пути от одной вершины до всех остальных во взвешенном графе.
Главное его преимущество перед алгоритмом Дейкстры в том, что он способен работать с отрицательными весами, НО имеет главный минус в производительности-работает за O(|V| × |E|), так как инициализация матрицы занимает время O(V) и на каждый проход надо V(E).

Случай 1: Граф без отрицательного цикла.
Для начала реализуем простейшую реализацию для графа без отрицательных весов, этот случай будет рассмотрен в другой статье. Увы, эта реализация будет бесконечно делать релаксацию, так как при суммарном весе цикла меньше 0, при обходе сколько угодно раз, длина кратчайшего пути будет выражаться большим по модулю отрицательным числом.

Итак, все действующие лица:

• Переменная numOfVertices обозначает количество вершин в графе.
• Переменная start нужна для обозначения номера начальной вершины.
• Вектор расстояний d[numOfVertices] который имеет размер такой же как и количество вершин в графе (numOfVertices), он хранит в себе ВСЕ КРАТЧАЙШИЕ РАССТОЯНИЯ от нашей стартовой вершины до ВСЕХ ДРУГИХ.
• Структура Edge (Ребро) для описания ребра, ясно, что ребро связывает вершину u с вершиной v и имеет вес w.

struct Edge {

 unsigned int u;

 unsigned int v;

 double w;

};

•  Будем использовать вектор для хранения ребер vector<Edge>EdgeList, так как к вектору удобно обращаться по индексу;
•  Переменная const double INFINITY=1E+10 для инициализации расстояний в начале работы функции.
• Введем функцию релаксации ребер Relax (unsigned int index, vector <double> &d) для того, чтобы алгоритм был более понятен, какой кусок кода за что отвечает. index-индекс текущего ребра, d - вектор расстояний.

void Relax (unsigned int index, vector <double> &d){

 if (d[EdgeList[index].v]>d[EdgeList[index].u]+EdgeList[index].w){

d[EdgeList[index].v]=d[EdgeList[index].u]+EdgeList[index].w;

}

}

          Процесс релаксации ребра заключается в проверке ребра на то, можно ли улучшить путь из вершины u в v.
Примеры с картиночками можно почитать у Кормена на странице 670.

Сам алгоритм состоит в том, чтобы:

1. Cначала инициализируем все расстояния бесконечными величинами, а расстояние стартовой вершины нулем.
2. Цикл for для каждой вершины
1. Вложенный цикл где для каждого ребра идет процесс релаксации
3. Вывод расстояний

Простейшая неоптимизированная реализация:

void Bellman_Ford_Shortest_Path(double start, unsigned int numOfVertices){

 vector<double> d (numOfVertices, INFINITY);

 d[start]=0;

 for (unsigned int i=0; i<numOfVertices-1; i++){

  for (unsigned int j=0; j<EdgeList.size();j++){

   Relax(j,d);//РЕЛАКСАЦИЯ РЕБРА

  }

 }

 for (int i=0; i<d.size(); i++){

  if (d[i]<INFINITY){ //ЕСЛИ ЕСТЬ ПУТЬ

   cout<<"vertex "<< i+1 <<") "<<d[i]<<endl;

  }

  else cout<<"vertex "<< i+1 <<") "<<"No way to this vertex"<<endl;

 }

}

Брр. тега <code> На блогспоте не вижу, очень неудобно внедрять код.

Read More