C++: поиск кратчайшего пути на графе

Поиск пути на графе - одна из самых распространённых проблем при реализации как серьёзных задач, так и игровых приложений. Приведу небольшой учебный пример того, как решить эту задачу максимально просто, то есть, рекурсивно :)

Граф представляет собой сеть из узлов-"городов" и соединяющих их путей-"дорог", при этом каждая "дорога" может иметь свой вес, соответствующий "расстоянию" между узлами, ну или "стоимости перевозки" между ними. Например, изображённый без весов граф может быть таким (все веса приняты за единицу):

пример плоского графа для теста программы поиска кратчайшего пути

Для описания одного пути подходит описанная в программе простая структура item, а весь граф - это просто массив map, состоящий из элементов item. Ещё проще было бы разместить всю информацию в матрице A размером n*n (n = числу узлов графа), каждый ненулевой элемент которой Ai,j соответствует весу пути из i-ой вершины в j-ую, но большинство элементов в такой матрице будут нулями, и она мне кажется избыточной.

Вот консольная реализация для Visual Studio 2010 или выше:

#include <iostream>
#include <windows.h>
using namespace std;

struct item { //структура для описания элемента карты
 int s,c; //начальный и конечный узлы
 int v; //"вес" пути
};

const int m = 9; //количество путей по графу
struct item map[m] = { //все пути, нумерация узлов с нуля
 {0,1,1}, {0,2,1}, {2,3,1}, {1,4,1}, {2,4,1},
 {4,5,1}, {4,7,1}, {5,6,1}, {6,7,1}
};
const int n = 8; //количество вершин графа
int road[n]; //номера узлов текущей "дороги"
bool incl[n]; //true, если i-ая вершина включена в путь
int way[n]; //искомый самый короткий путь
int waylen; //его длина
int start, finish; //начальная и конечная вершины
bool found;
int len; //найденный "вес" маршрута
int c_len; //текущий "вес" маршрута

int find (int s, int c) { //вес пути из s и c или 0, если пути нет
 for (int i=0; i<m; i++)
  if (map[i].s==s && map[i].c==c ||
      map[i].s==c && map[i].c==s) return map[i].v;
 return 0;
}

void step (int s, int f, int p) { //рекурсивный поиск шага пути
 int c; //номер вершины, куда делаем шаг
 if (s==f) { //путь найден
  found = true; //поставить флажок "найдено"
  len = c_len; //запомнить общий вес пути
  waylen = p; //запомнить длину пути (количество узлов)
  for (int i=0; i<waylen; i++) way[i] = road[i]; //запомнить сам путь
 }
 else { //выбор очередной точки
  for (c=0; c<n; c++) { //проверяем все вершины
   int w = find(s,c); //есть ли путь из s в c
   if (w && !incl[c] && (len==0 || c_len+w<len)) { //нужная точка не включена?
    road[p] = c; //включить точку в путь
    incl[c] = true; //пометить как включенную
    c_len += w; //учесть в общем весе пути
    step (c,f,p+1); //вызвать себя для поиска следующей точки
    road[p] = 0; //вернуть всё как было
    incl[c] = false;
    c_len -= w;
   }
  }
 }
}

int main () {
 //Инициализация данных:
 for (int i=0; i<n; i++) {
  road[i]=way[i]=0; incl[i] = false;
 }
 len = c_len = waylen = 0;

 start = 0; //начало пути - нумерация с 0
 finish = 7; //конец пути - нумерация с 0
 road[0] = start; //первую точку внесли в маршрут
 incl[start] = true; //и пометили как включённую
 found = false; //но путь пока не найден
 step (start,finish,1); //ищем вторую точку

 if (found) {
  cout << "Way is";
  for (int i=0; i<waylen; i++) cout << " " << way[i];
  cout << ", weight is " << len;
 }
 else cout << "Way not found!";
 cout << endl;
 system ("pause");
 return 0;
}

Примечания:

1. Нумерация узлов сделана с нуля, как принято в C++;

2. Если искомых путей с одинаковым общим весом len несколько, будет возвращён тот, что найден первым при лексикографическом (по номерам) порядке обхода вершин, например, 4-5-6, но не 4-7-6;

3. В тесте все веса одинаковы и равны 1, но должно работать и при разных;

4. Все пути предполагаются двусторонними, то есть, если есть дорога из i в j, то она есть и имеет тот же вес и из j в i. Если это не так, измените логику метода find:

if (map[i].s==s && map[i].c==c ||
    map[i].s==c && map[i].c==s) ... //пути "туда" и "обратно" равноценны и описаны вместе

if (map[i].s==s && map[i].c==c) ... //путь есть только "туда"

15.06.2015, 10:31 [26800 просмотров]