Блог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++

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

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

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

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