Skip to content
Snippets Groups Projects
Select Git revision
  • master default protected
  • 2.1.0
  • 2.1.1
  • 2.0.0
  • castelldefels
  • 1.0.1
  • 1.0.0
7 results
Blame Permalink
dijkstra.md 1.63 KiB

Dijktra algorithm

Description

This library provide a C++ implementation of the Dijkstra algorithm to find the lowest cost path between two points.

The function to compute the klowest cost path is called find_shortest_path and has the following prototype:

double find_shortest_path(Eigen::MatrixXd &graph,unsigned int start_node,unsigned int end_node,std::vector<unsigned int> &path)

where:

  • graph: is a 2D square matrix which represents the general connectivity of the nodes. That is, each row represents the connectivity of the corresponding node with all other nodes. The nodes that are not connected must be represented by a 0 value in the corresponding row and column. Any other value represent the cost of the connection.
  • start_node: the index of the starting node.
  • end_node: the index of the target node.
  • path: If a path is found, this vector has the sequence of nodes to reach the target node with lowest cost.

If a path to the target node is found, this function will return the total cost and also the sequence of nodes to reach it. If the path to the target node can not be found, this function returns the path to the last reachable node, and its cost.

How to use it.

  • Create an object of this class.
  • Generate a 2D square matrix representing the connectivity and cost of the desired problem.
  • Select a start and target nodes. With the current implementation, the start node msut always be the first one.
  • Call the find_shortest_path() function to get the desired path, if it exists.

An example is provided for a simple case.