алгоритм Дейкстры

[Шляпадляменя]

Реализовать алгоритм Дейкстры поиска кратчайшего пути между парой вершин во взвешенном графе.
Проблема с функцией построения пути. Сам алгоритм Дейкстры я написал.
BuildPath(Parent, s, e) - строит путь из вершины s в вершину e, проходя по ссылкам из Parent из e в s в обратном порядке. Если путь нельзя построить, возвращает признак отсутствия пути.

vector<int>BuildPath(map<int, int>  Parent, int s, int e) {
    vector<int> result;
    int i;
    i = e;
    //result.push_back(e);
    while (i != s) {
        result.push_back(Parent[i]);
        i = Parent[i];
      
    }
   // result.push_back(s);
    for (int j = 0; j < result.size() / 2; j++) {
        int k;
        k = result[j];
        result[j] = result[result.size() - 1 - j];
        k = result[result.size() - 1 - j];
    }
    return result;
}

Граф представляет собой:

#include <map>
#include <vector>
#include <tuple>
#include <initializer_list>

/**
 * Non-oriented weighted graph.
**/
class Graph {
public:
    Graph() {}
    Graph(std::initializer_list<std::tuple<int, int, double>> edges);

    /// Add single vertex to the graph.
    void add_vertex(int vertex);

    /// Add vertices (if necessary) and an edge between them to the graph.
    void add_edge(int start_vertex, int end_vertex, double weight = 1.0);

    /// Return all vertices of the graph.
    std::vector<int> get_vertices() const;

    /// Return all adjacent by edges vertices for the specified vertex.
    std::vector<int> get_adjacent_vertices(int src_vertex) const;

    /// Get adjacent edges for the vertex as vector of (end vertex, edge weight).
    std::vector<std::pair<int, double>> get_adjacent_edges(int src_vertex) const;

    /// Return true if the vertex exists in the graph, false otherwise.
    bool has_vertex(int vertex) const;

    /// Return true if vertices exist and have an edge between them, false otherwise.
    bool has_edge(int start_vertex, int end_vertex) const;

    /// Return weight of an edge between vertices (if there is any), throw an exception otherwise.
    double edge_weight (int start_vertex, int end_vertex) const;

    /// Remove the vertex and all its adjacent edges from the graph.
    void remove_vertex(int vertex);

    /// Remove the edge from the graph (but not the vertices).
    void remove_edge(int start_vertex, int end_vertex);

private:
    std::map<int, std::map<int, double>> vertices;
};

#include "graph.h"

#include <stdexcept>

using namespace std;

Graph::Graph(initializer_list<tuple<int, int, double>> edges) {
    for (const auto& e : edges) {
        add_edge(get<0>(e), get<1>(e), get<2>(e));
    }
}

void Graph::add_vertex(int vertex) {
    if (!has_vertex(vertex)) {
        vertices[vertex] = std::map<int, double>();
    }
}

void Graph::add_edge(int start_vertex, int end_vertex, double weight) {
    add_vertex(start_vertex);
    add_vertex(end_vertex);
    vertices[start_vertex][end_vertex] = weight;
    vertices[end_vertex][start_vertex] = weight;
}


std::vector<int> Graph::get_vertices() const {
    std::vector<int> result;
    for (const auto& p : vertices) {
        result.push_back(p.first);
    }
    return result;
}

std::vector<int> Graph::get_adjacent_vertices(int src_vertex) const {
    const auto it = vertices.find(src_vertex);
    if (it == vertices.end()) {
        return std::vector<int> {};
    }
    vector<int> result;
    for (const auto& p : it->second) {
        result.push_back(p.first);
    }
    return result;
}

vector<pair<int, double>> Graph::get_adjacent_edges(int src_vertex) const {
    const auto it = vertices.find(src_vertex);
    if (it == vertices.end()) {
        return vector<pair<int, double>> {};
    }
    vector<pair<int, double>> result;
    for (const auto& p : it->second) {
        result.push_back(make_pair(p.first, p.second));
    }
    return result;
}

bool Graph::has_vertex(int vertex) const {
    return (vertices.find(vertex) != vertices.end());
}

bool Graph::has_edge(int start_vertex, int end_vertex) const {
    const auto it = vertices.find(start_vertex);
    if (it == vertices.end()) {
        return false;
    }
    return (it->second.find(end_vertex) != it->second.end());
}

double Graph::edge_weight(int start_vertex, int end_vertex) const {
    const auto it_s = vertices.find(start_vertex);
    if (it_s == vertices.end()) {
        throw invalid_argument("Edge doesn't exist");
    }
    const auto it_e = it_s->second.find(end_vertex);
    if (it_e == it_s->second.end()) {
        throw invalid_argument("Edge doesn't exist");
    }
    return it_e->second;
}

void Graph::remove_vertex(int vertex) {
    /// Remove adjacent edges.
    auto adjacent_vertices = get_adjacent_vertices(vertex);
    for (const auto& adj_v : adjacent_vertices) {
        remove_edge(adj_v, vertex);
    }
    /// Remove the vertex itself.
    vertices.erase(vertex);
}

void Graph::remove_edge(int start_vertex, int end_vertex) {
    auto it_s = vertices.find(start_vertex);
    if (it_s != vertices.end()) {
        it_s->second.erase(end_vertex);
    }
    auto it_e = vertices.find(end_vertex);
    if (it_e != vertices.end()) {
        it_e->second.erase(start_vertex);
    }
}

[Пётр Седов]

Сообщение от Шляпадляменя

vector<int>BuildPath(map<int, int>  Parent, int s, int e) {

Вы передаёте map значению, поэтому весь контейнер копируется. Здесь это не надо, лучше передавать по const-ссылке:

vector<int> BuildPath(const map<int, int>& Parent, int s, int e) {

Сообщение от Шляпадляменя

    while (i != s) {
        result.push_back(Parent[i]);
        i = Parent[i];
      
    }

Не надо два раза делать поиск в map по одному и тому же ключу (i).

Сообщение от Шляпадляменя

    for (int j = 0; j < result.size() / 2; j++) {
        int k;
        k = result[j];
        result[j] = result[result.size() - 1 - j];
        k = result[result.size() - 1 - j];
    }

Во-первых, в последней строке присваивание должно быть наоборот:

result[result.size() - 1 - j] = k;

Во-вторых, весь этот цикл лучше заменить на вызов функции std::reverse:

#include <algorithm>

using namespace std;
...
reverse(result.begin(), result.end());

[Шляпадляменя]

спасибо, доделал. Теперь пытаюсь понять как мне генерировать Граф случайным образом, с учетом получения связного графа (с разными комбинациями числа вершин и ребер).
Получилось как-то так:

int main(int argc, char* argv[]) {
	Graph graph;
	vector<int> F;
	int start, end;
		start = rand() % 10;
		end = rand() % 10;
		for (int i = 0; i < 10; i++) {
			graph.add_edge(start, end);
		}
}

Не понимаю как его вывести

[Пётр Седов]

Сообщение от Шляпадляменя

Не понимаю как его вывести

Вывести на консоль? Или нарисовать?

[Шляпадляменя]

на консоль. С учетом того,что граф уже задан и есть некоторые его функции

[Пётр Седов]

Сообщение от Шляпадляменя

	int start, end;
		start = rand() % 10;
		end = rand() % 10;
		for (int i = 0; i < 10; i++) {
			graph.add_edge(start, end);
		}

Таким кодом вы 10 раз добавляете в граф одно и то же ребро. Чтобы добавлять разные рёбра, надо присваивания start и end внести внутрь цикла. И ещё хорошо бы проверять, что start ≠ end. Класс Graph позволяет добавлять странные рёбра (когда начало и конец -- это одна и та же вершина), но некоторые алгоритмы могут некорректно работать с такими графами.

Сообщение от Шляпадляменя

на консоль.

Можно так:

#include "graph.h"
#include <stdio.h>

using namespace std;

void print_graph(const Graph* graph) {
  vector<int> verts = graph->get_vertices();
  printf("vertices: ");
  bool need_sep = false;
  for (int v: verts) {
    if (need_sep) {printf(", ");} else {need_sep = true;}
    printf("%i", v);
  }
  printf("\n");

  printf("edges:\n");
  for (int v1: verts) {
    vector<pair<int, double>> edges = graph->get_adjacent_edges(v1);
    for (pair<int, double> e: edges) {
      int v2 = e.first;
      double w = e.second;
      if (v1 <= v2) { // граф неориентированный, поэтому «v1 -> v2» и «v2 -> v1» -- это одно и то же ребро
        printf("%i <-> %i, weight %f\n", v1, v2, w);
      }
    }
  }
}

[Шляпадляменя]

Спасибо большое, все работает.Как теперь мне узнать правильность работы функции shortest_path, как ее вывести? Через cout не работает.

int main() {
	srand(time(NULL));
	Graph g;
	int start, end;
	for (int i = 0; i < 10; i++) {
		start = rand() % 10;
		end = rand() % 10;
		if (start != end)
			g.add_edge(start, end,rand()%210/10.f);
	}
	vector<int> verts = g.get_vertices();
	printf("vertices: ");
	bool need_sep = false;
	for (int v : verts) {
		if (need_sep) { printf(", "); }
		else { need_sep = true; }
		printf("%i", v);
	}
	printf("\n");
	printf("edges:\n");
	for (int v1 : verts) {
		vector<pair<int, double>> edges = g.get_adjacent_edges(v1);
		for (pair<int, double> e : edges) {
			int v2 = e.first;
			double w = e.second;
			if (v1 <= v2) { // граф неориентированный, поэтому «v1 -> v2» и «v2 -> v1» -- это одно и то же ребро
				printf("%i <-> %i, weight %f\n", v1, v2, w);
			}
		}
	}
	auto t1 = std::chrono::high_resolution_clock::now();
	shortest_path(g, start,end);
	auto t2 = std::chrono::high_resolution_clock::now();
	auto time = std::chrono::duration<double>(t2 - t1).count();
	std::cout << "Time:" << time << " sec." << std::endl;
	
}

[Пётр Седов]

Шляпадляменя, в одной программе лучше не мешать stdio (printf) и iostreams (cout). Если вам iostreams больше нравится (или требуется по заданию), тогда его и будем использовать:

#include "graph.h"
#include <iostream>

using namespace std;

void print_graph(const Graph* graph) {
  vector<int> verts = graph->get_vertices();
  cout << "Vertices: ";
  bool need_sep = false;
  for (int v: verts) {
    if (need_sep) {cout << ", ";} else {need_sep = true;}
    cout << v;
  }
  cout << endl;

  cout << "Edges:" << endl;
  for (int v1: verts) {
    vector<pair<int, double>> edges = graph->get_adjacent_edges(v1);
    for (pair<int, double> e: edges) {
      int v2 = e.first;
      double w = e.second;
      if (v1 <= v2) { // граф неориентированный, поэтому «v1 -> v2» и «v2 -> v1» -- это одно и то же ребро
        cout << v1 << " <-> " << v2 << ", weight " << w << endl;
      }
    }
  }
}

Сообщение от Шляпадляменя

Как теперь мне узнать правильность работы функции shortest_path,

Можно тупо перебрать все возможные пути от start_vertex до target_vertex, и выбрать кратчайший. Вроде вот так должно работать:

#include <assert.h>
#include <float.h>

struct path_elem_t {
  path_elem_t* prev;
  int vertex;
  double sum_weight;
};

// во «взрослом» коде эти переменные надо засунуть в какой-нибудь struct context_t, и передавать везде указатель на этот struct
// в учебном задании проще использовать глобальные переменные
const Graph* _graph = nullptr;
int _target_vertex;
path_elem_t* _path_elems_last = nullptr; // связный список
int _path_index;
double _min_sum_weight;
int _best_path_index;

void gen_paths();
bool path_has_vertex(int vertex);
void handle_path();
void print_path(const path_elem_t* last);

void enum_all_paths(const Graph* graph, int start_vertex, int target_vertex) {
  _graph = graph;
  path_elem_t elem;
  elem.prev = nullptr;
  elem.vertex = start_vertex;
  elem.sum_weight = 0;
  _target_vertex = target_vertex;
  _path_index = 0;
  _min_sum_weight = DBL_MAX;
  _best_path_index = -1;
  assert(_path_elems_last == nullptr);
  _path_elems_last = &elem; // добавляем elem в список
  gen_paths();
  _path_elems_last = nullptr; // удаляем elem из списка
  if (_best_path_index != -1) {
    cout << "Best path: " << _best_path_index << ", sum weight = " << _min_sum_weight << "." << endl;
  } else {
    cout << "No paths." << endl;
  }
  _graph = nullptr;
}

void gen_paths() {
  if (_path_elems_last->vertex == _target_vertex) {
    handle_path();
    return;
  }
  vector<pair<int, double>> edges = _graph->get_adjacent_edges(_path_elems_last->vertex);
  for (pair<int, double> edge: edges) {
    int adjacent_vertex = edge.first;
    double weight = edge.second;
    if (!path_has_vertex(adjacent_vertex)) {
      path_elem_t elem;
      elem.prev = _path_elems_last;
      elem.vertex = adjacent_vertex;
      elem.sum_weight = _path_elems_last->sum_weight + weight;
      _path_elems_last = &elem; // добавляем elem в список
      gen_paths();
      _path_elems_last = elem.prev; // удаляем elem из списка
    }
  }
}

bool path_has_vertex(int vertex) {
  for (const path_elem_t* e = _path_elems_last; e != nullptr; e = e->prev) {
    if (e->vertex == vertex) {
      return true;
    }
  }
  return false;
}

void handle_path() {
  assert(_path_elems_last->vertex == _target_vertex);
  cout << "Path " << _path_index << ": ";
  print_path(_path_elems_last);
  double sum_weight = _path_elems_last->sum_weight;
  cout << "; sum weight = " << sum_weight << "." << endl;
  if (sum_weight < _min_sum_weight) {
    _min_sum_weight = sum_weight;
    _best_path_index = _path_index;
  }
  _path_index++;
}

void print_path(const path_elem_t* last) {
  if (last->prev != nullptr) {
    print_path(last->prev);
    cout << ", ";
  }
  cout << last->vertex;
}

Если ваша функция shortest_path выдаст такой же результат, значит скорее всего работает правильно .

Сообщение от Шляпадляменя

как ее вывести?

Если функция shortest_path возвращает std::vector<int>, то так:

vector<int> path = shortest_path();
cout << "Shortest path: ";
bool need_sep = false;
for (int v: path) {
  if (need_sep) {cout << ", ";} else {need_sep = true;}
  cout << v;
}
cout << endl;