Алгоритм Дейкстры на C++

Классический алгоритм Дейкстры широко применяется для поиска расстояний между рёбрами графов, и не только для этого. Скажем, его можно использовать в частном случае "определения путей в лабиринте", когда все веса рёбер одинаковы и равны, например, единице.

Правда, для графа из V рёбер (или поля из V игровых ячеек) размерность данных (матрицы смежности) будет V*V. Дополнительно функцией поиска выделяется 2*V ячеек памяти. Ниже приводится законченный пример, проверено в консоли Visual C++ 2010 (Файл, Создать, Проект, Win32, Консольное приложение Win32, выставить флажок "Пустой проект" и убрать "Предварительно откомпилированный заголовок"). После этого можно добавить в проект файл .cpp (Проект - Добавить новый элемент - Код - Файл C++) и вставлять код "как есть".

#include <iostream>
using namespace std;

const int V=6;

int *Dijkstra(int **GR, int V, int st) {
//Алгоритм Дейкстры - находит расстояние вершины номер st
//графа GR размерностью V	до всех остальных
//Вернет массив расстояний, INT_MAX - прохода нет
 int *distance, count, index, i, u;
 bool *visited;
 distance = new int [V];
 visited = new bool [V];
 for (i=0; i<V; i++) { distance[i]=INT_MAX; visited[i]=false; }
 distance[st]=0;
 for (count=0; count<V-1; count++) {
  int min=INT_MAX;
  for (i=0; i<V; i++)
  if (!visited[i] && distance[i]<=min) { min=distance[i]; index=i; }
  u=index;
  visited[u]=true;
  for (i=0; i<V; i++)
  if (!visited[i] && GR[u][i] && distance[u]!=INT_MAX &&
       distance[u]+GR[u][i]<distance[i])
   distance[i]=distance[u]+GR[u][i];
 }
 return distance;
}

void main() {
 setlocale(LC_ALL, "Rus");
 int start, **GR;
 GR = new int * [V];
 for (int i=0; i<V; i++) GR[i] = new int [V]; //инициализировали матрицу смежности GR
  
 int DATA[] = { //0 - нет связи, иначе положительный "вес" связи
  0, 1, 1, 0, 1, 0,
  0, 0, 0, 1, 0, 0,
  1, 0, 0, 1, 0, 0,
  0, 1, 1, 0, 0, 1,
  0, 0, 0, 0, 0, 1,
  0, 0, 0, 0, 0, 0
 };
 int i,j,k=0;
 for (i=0; i<V; i++)
 for (j=0; j<V; j++) GR[i][j]=DATA[k++];

 start=0; //начальная вершина, нумерация с 0

 int *distance=Dijkstra(GR, V, start);

 int m=start+1;
 cout << "Стоимость пути из начальной вершины до остальных:\n";
 for (i=0; i<V; i++) 
  if (distance[i]!=INT_MAX)
   cout << m << " > " << i+1 << " = " << distance[i] << endl;
  else cout << m << " > " << i+1 << " = " << "маршрут недоступен" << endl;

 system("pause>>void");
}

Модная реализация в стандарте C++11 (консоль Visual Studio 2015):

//Visual Studio 2015
#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <limits>
#include <set>
#include <utility>
#include <algorithm>
#include <iterator>
using namespace std;

typedef int vertex_t;
typedef double weight_t;

const weight_t max_weight = numeric_limits<double>::infinity();

struct neighbor {
 vertex_t target;
 weight_t weight;
 neighbor(vertex_t arg_target, weight_t arg_weight)
  : target(arg_target), weight(arg_weight) { }
};

typedef vector<vector<neighbor> > adjacency_list_t;


void DijkstraComputePaths(vertex_t source,
 const adjacency_list_t &adjacency_list, vector<weight_t> &min_distance,
 vector<vertex_t> &previous) {
 int n = adjacency_list.size();
 min_distance.clear();
 min_distance.resize(n, max_weight);
 min_distance[source] = 0;
 previous.clear();
 previous.resize(n, -1);
 set<pair<weight_t, vertex_t> > vertex_queue;
 vertex_queue.insert(make_pair(min_distance[source], source));

 while (!vertex_queue.empty()) {
  weight_t dist = vertex_queue.begin()->first;
  vertex_t u = vertex_queue.begin()->second;
  vertex_queue.erase(vertex_queue.begin());

  // Visit each edge exiting u
  const vector<neighbor> &neighbors = adjacency_list[u];
  for (vector<neighbor>::const_iterator neighbor_iter = neighbors.begin();
   neighbor_iter != neighbors.end();  neighbor_iter++)  {
   vertex_t v = neighbor_iter->target;
   weight_t weight = neighbor_iter->weight;
   weight_t distance_through_u = dist + weight;
   if (distance_through_u < min_distance[v]) {
    vertex_queue.erase(make_pair(min_distance[v], v));

    min_distance[v] = distance_through_u;
    previous[v] = u;
    vertex_queue.insert(make_pair(min_distance[v], v));
   }
  }
 }
}


list<vertex_t> DijkstraGetShortestPathTo(vertex_t vertex, 
  const vector<vertex_t> &previous) {
 list<vertex_t> path;
 for (; vertex != -1; vertex = previous[vertex])
  path.push_front(vertex);
 return path;
}


int main() {
 //запомнить пути в обеих направлениях в графе
 adjacency_list_t adjacency_list(6);
 // 0 = a
 adjacency_list[0].push_back(neighbor(1, 7));
 adjacency_list[0].push_back(neighbor(2, 9));
 adjacency_list[0].push_back(neighbor(5, 14));
 // 1 = b
 adjacency_list[1].push_back(neighbor(0, 7));
 adjacency_list[1].push_back(neighbor(2, 10));
 adjacency_list[1].push_back(neighbor(3, 15));
 // 2 = c
 adjacency_list[2].push_back(neighbor(0, 9));
 adjacency_list[2].push_back(neighbor(1, 10));
 adjacency_list[2].push_back(neighbor(3, 11));
 adjacency_list[2].push_back(neighbor(5, 2));
 // 3 = d
 adjacency_list[3].push_back(neighbor(1, 15));
 adjacency_list[3].push_back(neighbor(2, 11));
 adjacency_list[3].push_back(neighbor(4, 6));
 // 4 = e
 adjacency_list[4].push_back(neighbor(3, 6));
 adjacency_list[4].push_back(neighbor(5, 9));
 // 5 = f
 adjacency_list[5].push_back(neighbor(0, 14));
 adjacency_list[5].push_back(neighbor(2, 2));
 adjacency_list[5].push_back(neighbor(4, 9));

 vector<weight_t> min_distance;
 vector<vertex_t> previous;
 DijkstraComputePaths(0, adjacency_list, min_distance, previous);
 cout << "Distance from 0 to 4: " << min_distance[4] << endl;
 list<vertex_t> path = DijkstraGetShortestPathTo(4, previous);
 cout << "Path : ";
 copy(path.begin(), path.end(), ostream_iterator<vertex_t>(cout, " "));
 cout << endl;

 cin.get();
 return 0;
}

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

#include <iostream> 
#include <vector> 
#include <queue> 
#include <functional> 
using namespace std;

// Печать пути:
void printpath (vector<int>& parent, int vertex, int target) {
 if (vertex == 0) { return; }
 printpath(parent, parent[vertex], target);
 cout << vertex << (vertex == target ? "\n" : "--");
}

// Максимальный по весу путь:
int widest_path_problem
 (vector<vector<pair<int, int> > >& Graph, int src, int target) {
 vector<int> widest(Graph.size(), INT_MIN);
 vector<int> parent(Graph.size(), 0);
 priority_queue<pair<int, int>, vector<pair<int, int> >,
  greater<pair<int, int> > >
  container;
 container.push(make_pair(0, src));
 widest[src] = INT_MAX;
 while (container.empty() == false) {
  pair<int, int> temp = container.top();
  int current_src = temp.second;
  container.pop();
  for (auto vertex : Graph[current_src]) {
   int distance = max(widest[vertex.second],
    min(widest[current_src], vertex.first));
   if (distance > widest[vertex.second]) {
    widest[vertex.second] = distance;
    parent[vertex.second] = current_src;
    container.push(make_pair(distance, vertex.second));
   }
  }
 }

 printpath(parent, target, target);

 return widest[target];
}

int main() {
 vector<vector<pair<int, int> > > graph; //граф
 int no_vertices = 4; //количество вершин
 graph.assign(no_vertices + 1, vector<pair<int, int> >());
  // Вот наш граф визуально:
 // 1--2 
 // |  | 
 // 4--3 

 // Добавляем ребра в формате graph[вершина].push_back( 
 // make_pair(расстояние, другая_вершина) );
 graph[1].push_back(make_pair(1, 2));
 graph[1].push_back(make_pair(2, 4));
 graph[2].push_back(make_pair(3, 3));
 graph[4].push_back(make_pair(5, 3));
 //Ответ
 cout << widest_path_problem(graph, 1, 3);
  //аргументы - граф, вершина_1, вершина_2
 cin.get(); return 0;
}

06.01.2014, 18:19 [32833 просмотра]