math::DijkstrasAlgorithm Class Reference

Реализация алгоритма Дейкстры More...

#include <path_graph.h>

Collaboration diagram for math::DijkstrasAlgorithm:

Public Member Functions
	DijkstrasAlgorithm (PathWayGraph graph)
	Инициализирует новый экземпляр Dijkstras_algorithm.
double	Get_Min_Len () const
std::vector< std::size_t >	Get_Min_Path () const

Private Member Functions
void	CalculateMinPath_ ()
	Определяет длину кратчайшего пути из start_ в end_.

Private Attributes
std::size_t	first_point_
std::map< std::size_t, double >	graphs_vertex_
double	min_length_
std::vector< std::size_t >	min_path_
std::vector< std::shared_ptr< PathWayNode > >	path_nodes_
std::size_t	second_point_

Detailed Description

Реализация алгоритма Дейкстры

Constructor & Destructor Documentation

DijkstrasAlgorithm()

math::DijkstrasAlgorithm::DijkstrasAlgorithm ( PathWayGraph graph )

inline

Инициализирует новый экземпляр Dijkstras_algorithm.

Parameters

start	начальная точка
end	конечная точка

      : first_point_{graph.nodes.size() - 2},
        second_point_{graph.nodes.size() - 1},
        path_nodes_{graph.nodes},
        min_length_{0} {
    graphs_vertex_[first_point_] = 0;
    graphs_vertex_[second_point_] = inf;
    CalculateMinPath_();
  }

Here is the call graph for this function:

Member Function Documentation

CalculateMinPath_()

void math::DijkstrasAlgorithm::CalculateMinPath_ ( )

private

Определяет длину кратчайшего пути из start_ в end_.

                                           {
  while (graphs_vertex_[second_point_] > min_length_) {
    std::shared_ptr<PathWayNode> min_len_key;
    for (auto& elem : graphs_vertex_)
      if ((std::abs(elem.second - min_length_) <= precision) &&
          (!path_nodes_[elem.first]->is_visited))
        min_len_key = path_nodes_[elem.first];
 
    for (std::size_t i = 0; i < min_len_key->edges.size(); ++i)
      if ((graphs_vertex_.find(min_len_key->edges[i]->number) ==
           graphs_vertex_.end()) ||
          (graphs_vertex_[min_len_key->edges[i]->number] >
           graphs_vertex_[min_len_key->number] + min_len_key->edges_lens[i]))
        graphs_vertex_[min_len_key->edges[i]->number] =
            graphs_vertex_[min_len_key->number] + min_len_key->edges_lens[i];
      else
        continue;
    min_len_key->is_visited = true;
 
    min_length_ = inf;
    for (auto& elem : graphs_vertex_)
      if ((elem.second < min_length_) &&
          (!(*path_nodes_[elem.first]).is_visited))
        min_length_ = elem.second;
  }
 
  // Определение маршрута по длинам, сохранившимся в graphs_vertex_
  std::size_t end = second_point_;
  min_path_.push_back(end);
  while (end != first_point_) {
    for (std::size_t i = 0; i < path_nodes_[end]->edges.size(); ++i)
      if (std::abs(graphs_vertex_[path_nodes_[end]->number] -
                   graphs_vertex_[path_nodes_[end]->edges[i]->number] -
                   path_nodes_[end]->edges_lens[i]) <= precision) {
        end = path_nodes_[end]->edges[i]->number;
        min_path_.push_back(end);
        break;
      }
  }
  std::reverse(min_path_.begin(), min_path_.end());
}

Here is the caller graph for this function:

Get_Min_Len()

double math::DijkstrasAlgorithm::Get_Min_Len ( ) const

inline

{ return min_length_; }

Here is the caller graph for this function:

Get_Min_Path()

std::vector< std::size_t > math::DijkstrasAlgorithm::Get_Min_Path ( ) const

inline

{ return min_path_; }

Here is the caller graph for this function:

Member Data Documentation

first_point_

std::size_t math::DijkstrasAlgorithm::first_point_

private

graphs_vertex_

std::map<std::size_t, double> math::DijkstrasAlgorithm::graphs_vertex_

private

min_length_

double math::DijkstrasAlgorithm::min_length_

private

min_path_

std::vector<std::size_t> math::DijkstrasAlgorithm::min_path_

private

path_nodes_

std::vector<std::shared_ptr<PathWayNode> > math::DijkstrasAlgorithm::path_nodes_

private

second_point_

std::size_t math::DijkstrasAlgorithm::second_point_

private

---

The documentation for this class was generated from the following files:

• math/optimal_way/path_graph.h
• math/optimal_way/path_graph.cpp