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

Помощь дата->рейтинг Поиск Почта RSS канал Статистика nickolay.info Домой

Алгоритм Дейкстры на 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;
}

теги: c++ алгоритм

показать комментарии (1)

06.01.2014, 18:19; рейтинг: 20247

  свежие записипоиск по блогукомментариистатистикао "вирусах" в архивах .zip

Наверх Яндекс.Метрика
© PerS
вход