becks
@becks

В чем ошибка построения кратчайшего пути с помощью BGL (boost graph library)?

Пытаюсь с помощью BGL найти в графе кратчайший путь из одной вершины до всех остальных. Написал такой код:
#include <iostream>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/property_map.hpp>
 
#include"cdu/CduNetworkModeExtractor.h"
 
usingnamespace std;
usingnamespace boost;
 
typedefadjacency_list <listS, vecS, directedS, no_property, property<edge_weight_t, int>> Graph;
typedefgraph_traits<Graph>::vertex_descriptor VertexDescriptor;
typedefstd::pair<int,int> Edge;
 
int main()
{
	...	
	//----Graph----
	QVector<ElectricityEdge> q_edges = mode.edges;
	vector<Edge> edges;
	
	foreach(ElectricityEdgee, q_edges)
		edges.push_back(Edge(e.sourceNode, e.destNode));

	std::vector<int> weights(edges.size(), 1);
	
	Graph graph(edges.begin(), edges.end(), weights.begin(), mode.nodes.size());
	
	vector<VertexDescriptor> p( num_vertices(graph) );
	vector<int> distance( num_vertices(graph) );
	VertexDescriptor s = vertex(1,graph);
	
	dijkstra_shortest_paths(graph, s, predecessor_map(&(*p.begin())).distance_map(&(*distance.begin())));
	
	graph_traits<Graph>::vertex_iterator vi,vend;
	boost::tie(vp,vend)=vertices(graph);
	
	std::for_each(vp, vend, [&distance](int value)
				{ std::cout << "distanceto" << value << "equalto" << distance[value] << "\n"; }
	);
	---------
	return 0;
}


Код не работает корректно. Причиной тому, сколько понял, является отсутствие последовательной нумерации узлов в графе. Т.е. в графе могут быть узлы с номерами 15, 17, 23 , а узлов 16, 18-22 нет. На тестовом примере максимальный номер узла 900451, а реальное число узлов 4511. Однако num_vertices(graph) возвращает 900452 (или 900451, не помню). Отсюда сделал вывод, что он считает по максимальному номеру узла.

Подскажите, пожалуйста, как правильно поправить пример. Единственный выход сейчас вижу, делать карту соответствий последовательный номер - реальный номер узла.
  • Вопрос задан
  • 437 просмотров
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы