Find missing number (in C++)

Find missing number

Like the missing number problem, but given a list of N integers and these integers are in the range of [X, Y].
There are no duplicates in list. Maybe one or more than one of the integers is missing in the list.
Write an efficient code to find the first missing integer

— use binary search method:

/**
 * find the missing number (the first one) in a sorted array (min to max).
 * @tparam T integral value type,
 * @param nums the sorted numbers to find missing number.
 * @param nNums number count of @a nums.
 * @param rangeMin to find the number is this range.
 * @param rangeMax to find the number is this range.
 * @param[out] result result when success.
 * @return true when success, false when params invalid.
 *
 * @note
 * - @a nums should NOT nil, valid and sorted.
 * - @a nNums should valid.
 * - rangeMin should less than rangeMax!
 */
template<typename T>
typename CPPBASE2_ENABLE_IF<CPPBASE2_IS_INTEGRAL<T>::value, bool>::type
searchFirstMissingNumber(
  const T* const nums,
  const size_t nNums,
  const T rangeMin,
  const T rangeMax,
  T& result) {
  if ((!nums) || (rangeMin >= rangeMax)) {
    return false;
  }
  const T n = (rangeMax - rangeMin) + 1;
  if (uint64_t(n) <= nNums) {
    return false;
  }
  if (nNums < 1) {
    result = rangeMin;
    return true;
  }

  size_t leftIdx = 0;
  size_t rightIdx = nNums - 1;
  T expectMin = rangeMin;
  //T expectMax = rangeMax;
  size_t midIdx;
  T expectMid;

  // e.g.1: [0, 9], {0, 1, 2, 3, 5, 6, 7, 8, 9}
  //     2: [0, 9], {0, 1, 2, 4, 5, 6, 7, 8, 9}
  //     3: [0, 9], {0, 1, 2, 3, 4, 6, 7, 8, 9}
  //     4: [0, 9], {7, 8}
  //     5: [0, 9], {9}
  //     6: [0, 9], {0}
  //     7: [0, 9], {0, 1, 2, 3, 4, 5, 7, 8, 9}
  //     8: [-3, 5], {-3, -2, -1, 2, 3, 4, 5}
  while (leftIdx <= rightIdx) {
    if (nums[leftIdx] > expectMin) {
      result = expectMin;
      return true;
    } else {
      midIdx = (leftIdx + rightIdx) / 2;
      expectMid = rangeMin + midIdx;
      const T& midNum = nums[midIdx];
      if ((midNum == expectMid)
        && ((midIdx >= rightIdx) || ((expectMid + 1) != nums[midIdx + 1]))) {
        result = expectMid + 1;
        return true;
      } else if (midNum > expectMid) {
        // search left
        rightIdx = midIdx - 1;
        //expectMax = midNum - 1;
        continue;
      }
      // search right
      leftIdx = midIdx + 1;
      expectMin = midNum + 1;
    }
  }

  throw std::logic_error("bug!");
  return false;
}

some test code:

TEST(m, large) {
  const int N = 1024 * 1024 * 100;
  std::vector<int> a;
  a.reserve(N);
  SteadyTime t1, t2;

  const Duration maxET = Duration::milliseconds(1);
  Duration sum1, sum2;

  for (int k = 0; k < 100; ++k) {
    int missingNumber = kRg->get32() % a.capacity();
    int missingNumber2 = kRg->get32() % a.capacity();
    if (missingNumber > missingNumber2) {
      std::swap(missingNumber, missingNumber2);
    }
    int offset = kRg->get32() % a.capacity();
    if (k % 2) {
      offset *= -1;
    }
    a.clear();
    for (int i = 0; i < N; ++i) {
      if (i != missingNumber && i != missingNumber2) {
        a.push_back(offset + i);
      }
    }
    int result = -1;
    t1 = SteadyTime::now();
    EXPECT_TRUE(algorithm::searchFirstMissingNumberSlow(
      a.data(), a.size(), offset, offset + (N - 1), result));
    t2 = SteadyTime::now();
    sum1 += (t2 - t1);

    EXPECT_EQ(offset + missingNumber, result);
    EXPECT_LE((t2 - t1), Duration::milliseconds(100));

    CPPBASE2_INFO("searchFirstMissingNumberSlow"
           " size " << a.size()
      << ", elapsed time " << (t2 - t1).toNanosec() << " ns, "
      << ", result = " << (offset + missingNumber));

    result = -1;
    t1 = SteadyTime::now();
    EXPECT_TRUE(algorithm::searchFirstMissingNumber(
      a.data(), a.size(), offset, offset + (N - 1), result));
    t2 = SteadyTime::now();
    sum2 += (t2 - t1);

    EXPECT_EQ(offset + missingNumber, result);
    EXPECT_LE((t2 - t1), maxET);

    CPPBASE2_INFO("searchFirstMissingNumber"
           " size " << a.size()
      << ", elapsed time " << (t2 - t1).toNanosec() << " ns, "
      << ", result = " << (offset + missingNumber));
  }

  EXPECT_LE((sum1.toNanosec() / 100), Duration::milliseconds(20).toNanosec());
  EXPECT_GE((sum1.toNanosec() / 100), Duration::milliseconds(5).toNanosec());
  EXPECT_LE((sum2.toNanosec() / 100), Duration::microseconds(10).toNanosec());
}

Draw line primitives

Draw line primitives

在栅格图中找到两点间的栅格(栅格图坐标), 这些点是两个点构成的线段经过的栅格, 使用算法:
Bresenham's_line_algorithm.

See also:


Implementation:

NOTE: Algorithm and implementation for integer arithmetic.

/**
 * Draw the segment with a Brush instance.
 * Implements in Bresenham's line algorithm: is a line drawing algorithm
 * that determines the points of an n-dimensional raster that should be
 * selected in order to form a close approximation to a straight line
 * between two points.
 * It is commonly used to draw line primitives in a bitmap image
 * (e.g. on a computer screen), as it uses only integer addition,
 * subtraction and bit shifting, all of which are very cheap operations
 * in standard computer architectures.
 * @tparam Brush the brush to draw, operator()(x, y) requried.
 * @param brush the brush instance.
 * @note
 * - Scalar should be integer!
 * - n should >= 2, this method for 2D, only use x and y.
 * - operator()(x, y) for Brush requried.
 * @return drawed count.
 * @sa
 * - https://en.wikipedia.org/wiki/Bresenham's_line_algorithm
 * - https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm#All_cases
 * - costmap_2d/include/costmap_2d/costmap_2d.h
 */
template<typename Brush>
uint32_t draw2D(const Brush& brush) const noexcept
{
    // Tparams check
    static_assert(2 == n || 3 == n, "n should be 2 or 3");
    static_assert(
        std::is_integral<typename std::decay<Scalar>::type>::value,
        "Scalar should be integer");
    // Draw
    uint32_t ndrawed = 0;
    // Cover gradients between 0 and -1 by checking whether y needs to
    // increase or decrease (i.e. dy < 0).
    const auto draw2DLow = [&brush, &ndrawed](const P& a, const P& b) {
        Scalar dx = b(0) - a(0);
        Scalar dy = b(1) - a(1);
        Scalar yi;
        if (dy < 0) {
            yi = -1;
            dy = -dy;
        } else {
            yi = 1;
        }
        const Scalar ddx = 2 * dx;
        const Scalar ddy = 2 * dy;
        Scalar D = ddy  - dx;
        Scalar y = a(1);
        for (const Scalar& x : Range<Scalar>{ a(0), b(0) }) {
            brush(x, y);
            ++ndrawed;
            if (D > 0) {
                y += yi;
                D -= ddx;
            }
            D += ddy;
        }
    };
    // By switching the x and y axis an implementation for positive or negative
    // steep gradients can be written as:
    const auto draw2DHigh = [&brush, &ndrawed](const P& a, const P& b) {
        Scalar dx = b(0) - a(0);
        Scalar dy = b(1) - a(1);
        Scalar xi;
        if (dx < 0) {
            xi = -1;
            dx = -dx;
        } else {
            xi = 1;
        }
        const Scalar ddx = 2 * dx;
        const Scalar ddy = 2 * dy;
        Scalar D = ddx  - dy;
        Scalar x = a(0);
        for (const Scalar& y : Range<Scalar>{ a(1), b(1) }) {
            brush(x, y);
            ++ndrawed;
            if (D > 0) {
                x += xi;
                D -= ddy;
            }
            D += ddx;
        }
    };
    // Need to detect whether x1 > x0 or y1 > y0 and reverse the input
    // coordinates before drawing
    if (std::abs(this->b(1) - this->a(1)) < std::abs(this->b(0) - this->a(0))) {
        if (this->a(0) > this->b(0)) {
            draw2DLow(this->b, this->a);
        } else {
            draw2DLow(this->a, this->b);
        }
    } else {
        if (this->a(1) > this->b(1)) {
            draw2DHigh(this->b, this->a);
        } else {
            draw2DHigh(this->a, this->b);
        }
    }
    return ndrawed;
}

Test and example:

TEST(Segment, draw2D)
{
    Segment<int32_t, 2> segment{ Eigen::Vector2i{ 3, 1 }, Eigen::Vector2i{ -6, -4 } };
    const std::vector<Eigen::Vector2i> expect{
        Eigen::Vector2i{ -6, -4 },
        Eigen::Vector2i{ -5, -3 },
        Eigen::Vector2i{ -4, -3 },
        Eigen::Vector2i{ -3, -2 },
        Eigen::Vector2i{ -2, -2 },
        Eigen::Vector2i{ -1, -1 },
        Eigen::Vector2i{ 0,  -1 },
        Eigen::Vector2i{ 1,  0 },
        Eigen::Vector2i{ 2,  0 },
        Eigen::Vector2i{ 3,  1 } };
    std::vector<Eigen::Vector2i> ps;
    const auto brush = [&ps](const int32_t x, const int32_t y) {
        std::cout << x << ' ' << y << '\n';
        ps.emplace_back(Eigen::Vector2i{ x, y });
    };
    ps.clear();
    EXPECT_EQ(expect.size(), segment.draw2D(brush));
    EXPECT_EQ(expect.size(), ps.size());
    if (expect.size() == ps.size()) {
        for (uint32_t i = 0; i < ps.size(); ++i) {
            EXPECT_EQ(expect[i], ps[i]);
        }
    }
    //
    Segment<int32_t, 3> s3;
    ps.clear();
    s3.draw2D(brush);
    EXPECT_EQ(1u, ps.size());
    if (1u == ps.size()) {
        EXPECT_EQ((Eigen::Vector2i{ 0, 0 }), ps[0]);
    }
    // BAD test:
    //Segment<double, 3> badS3;
    //badS3.draw2D(brush);
}

draw2D-example.png

Dijkstra’s algorithm

Dijkstra’s algorithm

【原文】

#

NOTE: Dijkstra == Astar when heuristicCostEstimate() of Astar return 0!!

Dijkstra’s algorithm to find the shortest path between a and b.
It picks the unvisited vertex with the lowest distance,
calculates the distance through it to each unvisited neighbor,
and updates the neighbor’s distance if smaller.
Mark visited (set to red) when done with neighbors.

Name Value
Class Search algorithm
Data structure Graph
Worst-case performance

实现

Pseudocode

In the following algorithm, the code u ← vertex in Q with min dist[u],
searches for the vertex u in the vertex set Q that has the least dist[u] value. length(u, v) returns the length of the edge joining (i.e. the distance between) the two neighbor-nodes u and v.
The variable alt on line 18 is the length of the path from the root node to the neighbor node v if it were to go through u.
If this path is shorter than the current shortest path recorded for v,
that current path is replaced with this alt path.
The prev array is populated with a pointer to the “next-hop” node on the
source graph to get the shortest route to the source.

Using a priority queue

A min-priority queue is an abstract data type that provides 3 basic operations:
add_with_priority(), decrease_priority() and extract_min().
As mentioned earlier, using such a data structure can lead to faster computing times than using a basic queue.
Notably, Fibonacci heap (Fredman & Tarjan 1984) or Brodal queue offer optimal implementations for those 3 operations.
As the algorithm is slightly different, we mention it here, in pseudo-code as well:

An implementation with min priority queue

NOTE when implements, data structure is min priority(heap), so min ls back()!

/**
* @file dijkstra.hpp
* @author y.
*/
#pragma once
#include <unordered_map> // unordered_map
#include <limits> // numeric_limits
#include <algorithm> // push_heap ..
namespace yuiwong
{
/**
* @struct DijkstraGraph
* Graph for dijkstra algorithm implementation
*
* @note
* - Dijkstra == Astar when heuristicCostEstimate() of Astar return 0
* - NOT for MT (NOT MT-safe)
*
* @tparam Id vertex ID type, id to identify a unique vertex, default
* int32_t
* @tparam Edge edge distance type, default double, the distance is
* distance of the edge of vertex a and vertex b
*/
template<typename Id = int32_t, typename Edge = double>
struct DijkstraGraph {
   using Distance = Edge;///< Distance alias
   /**
    * Edges type of a vertex: { destVertexId, Distance }
    * @note destVertexId should NOT == id of this vertex, else distance
    * should be 0
    */
   using Edges = std::unordered_map<Id, Distance>;
   /// Vertices type of a graph for dijkstra: { VertexId, Edges }
   using Vertices = std::unordered_map<Id, Edges>;
   /// Dtor
   ~DijkstraGraph() noexcept;
   /**
    * Check whether has vertex of id
    * @param id vertex id
    * @return true if vertex found, else false
    */
   inline bool hasVertex(Id const& id) const noexcept;
   /**
    * Check whether has edge of vertex of id to vertex of destVertexId
    * @param id vertex id
    * @param destVertexId dest vertex id
    * @return true if edge found, else false
    */
   bool hasEdge(Id const& id, Id const& destVertexId) const noexcept;
   //bool addVertex(Id const& id, Edges&& edges) noexcept;
   //bool addVertex(Id const& id, Edges const& edges) noexcept;
   /**
    * Add dest vertex for this vertex with distance and override check
    * @note
    * - edge only for vertex -> dest vertex
    * - NOT need to add vertex a -> a with distance == 0
    * @param id this vertex id
    * @param destVertexId dest vertex id
    * @param edge the distance of this vertex to dest vertex, i.e.
    * the edge of this vertex -> dest vertex
    * @return true when add successfully, false when @a destVertexId
    * exists or @a distance invalid
    * @sa
    * - hasEdge
    * - updateVertex
    */
   virtual bool addVertex(
       Id const& id,
       Id const& destVertexId,
       Edge const& edge) noexcept;
   /**
    * Add or update dest vertex for this vertex with distance check
    * @note
    * - edge only for vertex -> dest vertex
    * - NOT need to add vertex a -> a with distance == 0
    * @param id this vertex id
    * @param destVertexId dest vertex id
    * @param edge the distance of this vertex to dest vertex, i.e.
    * the edge of this vertex -> dest vertex
    * @return true when add successfully, false when @a distance invalid
    * @sa
    * - hasEdge
    * - addVertex
    */
   virtual bool updateVertex(
       Id const& id,
       Id const& destVertexId,
       Edge const& edge) noexcept;
   /**
    * Get edge distance of this vertex to dest vertex
    * @param id this vertex id
    * @param destVertexId dest vertex id
    * @return distance when both vertex and edge exists
    * @throw std::logic_error when vertex or dest vertex NOT exists
    */
   Distance getEdge(Id const& id, Id const& destVertexId) const;
   /**
    * Get edges of this vertex
    * @param id this vertex id
    * @return edges of this vertex
    * @throw std::logic_error when vertex NOT exists
    */
   Edges const& getEdges(Id const& id) const;
   /// @return vertices
   inline Vertices const& getVertices() const noexcept;
   /// @return vertices size
   inline uint32_t getSize() const noexcept;
   /// Clear vertices
   inline void clear() noexcept;
   /// Remove vertex by @a id
   bool removeVertex(Id const& id) noexcept;
   /// Remove edge of vertex of @a id -> vertex of @a destVertexId
   bool removeEdge(Id const& id, Id const& destVertexId) noexcept;
protected:
   Vertices vertices;///< Graph vertices
};
/**
* @struct Dijkstra
* Dijkstra algorithm implementation
*
* @note NOT for MT (NOT MT-safe)
* @tparam Graph graph type for Dijkstra
* @tparam Id vertex ID type, id to identify a unique vertex, default
* int32_t
* @tparam Edge edge distance type, default double, the distance is
* distance of the edge of vertex a and vertex b
*
* @sa https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
*/
template<typename Id = int32_t, typename Edge = double>
struct Dijkstra {
   using Distance = Edge;///< Distance alias
   /**
    * Compute shortest path from @a start to @a goal
    * @note
    * - Using a min priority queue
    *   (NOTE when implements, data structure is min priority queue(heap),
    *   so min ls back()!)
    * - Only when @a start == @a goal, then result has 1 vertex, else
    *   result > 1 vertex
    * @param graph graph to compute shortest path
    * @param start start vertex id
    * @param goal goal vertex id
    * @param[out] distance if NOT nil set to total distance when success
    * @return shortest path when success (NOT empty)
    * @throw std::logic_error when start or goal invalid or cannot find path
    * @sa
    * - https://en.wikipedia.org/wiki/Dijkstra's_algorithm#Pseudocode
    * - https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Using_a_priority_queue
    */
   template<typename Graph>
   typename std::enable_if<
       std::is_base_of<DijkstraGraph<Id, Edge>, Graph>::value
       || std::is_same<DijkstraGraph<Id, Edge>, typename std::decay<Graph>::type>::value,
       std::vector<Id> >::type solve(
       Graph const& graph,
       Id const& start,
       Id const& goal,
       Distance* const distance = nullptr) const;
};
/// Int32_t + double dijkstra implements
using DijkstraId = Dijkstra<int32_t, double>;
/// String + double dijkstra implements
using DijkstraSd = Dijkstra<std::string, double>;
template<typename Id, typename Edge>
DijkstraGraph<Id, Edge>::~DijkstraGraph() noexcept {}
template<typename Id, typename Edge>
inline bool DijkstraGraph<Id, Edge>::hasVertex(Id const& id) const noexcept
{
   return this->vertices.find(id) != this->vertices.cend();
}
template<typename Id, typename Edge>
bool DijkstraGraph<Id, Edge>::hasEdge(
   Id const& id, Id const& destVertexId) const noexcept
{
   auto const eit = this->vertices.find(id);
   if (eit == this->vertices.cend()) {
       return false;
   }
   auto const& edges = eit->second;
   return edges.find(destVertexId) != edges.cend();
}
template<typename Id, typename Edge>
bool DijkstraGraph<Id, Edge>::addVertex(
   Id const& id, Id const& destVertexId, Edge const& edge) noexcept
{
   // Check 0
   if ((id == destVertexId)
       && (std::abs(edge) > std::numeric_limits<Distance>::epsilon())) {
       return false;
   }
   // Check exists
   auto const eit = this->vertices.find(id);
   if (eit != this->vertices.end()) {
       auto const& edges = eit->second;
       if (edges.find(destVertexId) != edges.end()) {
           return false;
       }
   }
   // Add
   this->vertices[id][destVertexId] = edge;
   return true;
}
template<typename Id, typename Edge>
bool DijkstraGraph<Id, Edge>::updateVertex(
   Id const& id, Id const& destVertexId, Edge const& edge) noexcept
{
   // Check 0
   if ((id == destVertexId)
       && (std::abs(edge) > std::numeric_limits<Distance>::epsilon())) {
       return false;
   }
   // Add or update
   this->vertices[id][destVertexId] = edge;
   return true;
}
template<typename Id, typename Edge>
typename DijkstraGraph<Id, Edge>::Distance
DijkstraGraph<Id, Edge>::getEdge(Id const& id, Id const& destVertexId) const
{
   auto const eit = this->vertices.find(id);
   if (eit == this->vertices.cend()) {
       throw std::logic_error("this vertex NOT exists");
   }
   auto const& edges = eit->second;
   auto const edit = edges.find(destVertexId);
   if (edit == edges.cend()) {
       throw std::logic_error("dest vertex NOT exists");
   }
   return edit->second;
}
template<typename Id, typename Edge>
typename DijkstraGraph<Id, Edge>::Edges const&
DijkstraGraph<Id, Edge>::getEdges(Id const& id) const
{
   auto const eit = this->vertices.find(id);
   if (eit == this->vertices.cend()) {
       throw std::logic_error("this vertex NOT exists");
   }
   return eit->second;
}
template<typename Id, typename Edge>
inline typename DijkstraGraph<Id, Edge>::Vertices const&
DijkstraGraph<Id, Edge>::getVertices() const noexcept
{
   return this->vertices;
}
template<typename Id, typename Edge>
inline uint32_t DijkstraGraph<Id, Edge>::getSize() const noexcept
{
   return this->vertices.size();
}
template<typename Id, typename Edge>
inline void DijkstraGraph<Id, Edge>::clear() noexcept
{
   this->vertices.clear();
}
template<typename Id, typename Edge>
inline bool DijkstraGraph<Id, Edge>::removeVertex(Id const& id) noexcept
{
   auto it = this->vertices.find(id);
   if (it != this->vertices.end()) {
       this->vertices.erase(it);
       return true;
   }
   return false;
}
template<typename Id, typename Edge>
inline bool DijkstraGraph<Id, Edge>::removeEdge(
   Id const& id, Id const& destVertexId) noexcept
{
   auto it = this->vertices.find(id);
   if (it != this->vertices.end()) {
       auto eit = it->second.find(destVertexId);
       if (eit != it->second.end()) {
           it->second.erase(eit);
           if (it->second.empty()) {
               this->vertices.erase(it);
           }
           return true;
       }
   }
   return false;
}
/// Operator<< for DijkstraGraph
template<typename Id, typename Edge>
std::ostream& operator<<(std::ostream& os, DijkstraGraph<Id, Edge> const& g) noexcept
{
   os << '(' << g.getSize() << ") ";
   for (auto const& v : g.getVertices()) {
       for (auto const& e : v.second) {
           os << v.first << "->" << e.first << ':' << e.second << ";";
       }
       os << "; ";
   }
   return os;
}
template<typename Id, typename Edge>
template<typename Graph>
typename std::enable_if<
   std::is_base_of<DijkstraGraph<Id, Edge>, Graph>::value
   || std::is_same<DijkstraGraph<Id, Edge>, typename std::decay<Graph>::type>::value,
   std::vector<Id> >::type Dijkstra<Id, Edge>::solve(
   Graph const& graph,
   Id const& start,
   Id const& goal,
   Distance* const distance) const
{
   //// Check start and goal
   //if (!this->graph.hasVertex(start) || !this->graph.hasVertex(goal)) {
   //    throw std::logic_error("start or goal invalid");
   //}
   std::unordered_map<Id, Distance> distances;
   auto const comparator = [&distances](Id const& left, Id const& right) {
       return distances[left] > distances[right];
   };
   std::vector<Id> nodes;
   auto const maxd = std::numeric_limits<Distance>::max();
   // Initialization
   for (auto const& vertex : graph.getVertices()) {
       if (vertex.first == start) {
           // Distance from source to source
           distances[start] = Distance(0);
       } else {
           // Unknown distance from source to v
           distances[vertex.first] = maxd;
       }
       // Add vertex to Q: Q.add_with_priority(v, dist[v])
       // All nodes initially in Q (unvisited nodes)
       // Max is first, min is last
       nodes.push_back(vertex.first);
       std::push_heap(nodes.begin(), nodes.end(), comparator);
   }
   // Previous node in optimal path from source
   std::unordered_map<Id, Id> previous;
   // The main loop
   std::vector<Id> path;
   auto const eps = std::numeric_limits<Distance>::epsilon();
   while (!nodes.empty()) {
       // Node with the least distance will be selected first
       // If comparator is less => removes the largest element from a max heap,
       // but here comparator is greater => removes smallest
       std::pop_heap(nodes.begin(), nodes.end(), comparator);
       Id smallest = nodes.back();
       nodes.pop_back();
       // Check whether done
       if (goal == smallest) {
           // Fill path from goal to start(NO start)
           //auto const end = previous.end();
           //while (previous.find(smallest) != end) {
           //    path.push_back(smallest);
           //    smallest = previous[smallest];
           //}
           for (auto it = previous.find(smallest), end = previous.end();
               it != end; it = previous.find(smallest)) {
               path.push_back(smallest);
               smallest = it->second;
           }
           break;
       }
       // Check whether start or goal invalid
       if (std::abs(maxd - distances[smallest]) <= eps) {
           throw std::logic_error("start or goal invalid 2");
           //break;
       }
       // Where neighbor is still in Q
       auto const& edges = graph.getEdges(smallest);
       //for (auto const& neighbor : graph.vertices[smallest]) {...}
       for (auto const& neighbor : edges) {
           // alt ← dist[u] + length(u, v)
           Distance alt = distances[smallest] + neighbor.second;
           // A shorter path to neighbor vertex has been found
           auto const& nei = neighbor.first;
           if (alt < distances[nei]) {
               distances[nei] = alt;
               previous[nei] = smallest;
               // Q.decrease_priority(v, alt) (alt has updated to distances):
               std::make_heap(nodes.begin(), nodes.end(), comparator);
           }
       }
   }
   // Check whether unreachable
   if (path.empty() && (start != goal)) {
       throw std::logic_error("cannot find path");
   }
   // Add start to back
   path.push_back(start);
   // Reverse to start->goal
   std::reverse(path.begin(), path.end());
   // Done successfully
   if (distance) {
       *distance = distances[goal];
   }
   return std::move(path);
}
} // namespace yuiwong

Dijkstra test

TEST(Dijkstra, solve)
{
    Dijkstra<int32_t, double> dijkstra;
    DijkstraGraph<int32_t, double> g;
    EXPECT_FALSE(g.hasVertex(0));
    EXPECT_FALSE(g.hasVertex(-1));
    EXPECT_FALSE(g.hasVertex(100));
    EXPECT_FALSE(g.hasVertex(3));
    EXPECT_FALSE(g.hasEdge(0, -1));
    EXPECT_FALSE(g.hasEdge(0, 100));
    EXPECT_FALSE(g.hasEdge(0, 3));
    EXPECT_THROW(g.getEdge(0, -1), std::logic_error);
    //
    EXPECT_TRUE(g.addVertex(0, -1, 3.2));
    EXPECT_FALSE(g.addVertex(0, -1, 3.3));
    EXPECT_DOUBLE_EQ(g.getEdge(0, -1), 3.2);
    EXPECT_TRUE(g.updateVertex(0, -1, 3.3));
    EXPECT_DOUBLE_EQ(g.getEdge(0, -1), 3.3);
    EXPECT_TRUE(g.addVertex(0, 3, 200));
    EXPECT_TRUE(g.addVertex(-1, 3, 20));
    EXPECT_TRUE(g.addVertex(100, 3, 10));
    EXPECT_TRUE(g.addVertex(3, 100, 11.23));
    EXPECT_TRUE(g.addVertex(3, 5, -10));
    EXPECT_TRUE(g.addVertex(5, 7, 2));
    EXPECT_FALSE(g.addVertex(7, 7, 2e3));
    EXPECT_TRUE(g.addVertex(7, 7, 0));
    //
    double d = -1;
    auto path = dijkstra.solve(g, -1, 100, &d);
    for (auto const& p : path) {
        std::cout << p << '\n';
    }
    std::cout << "d: " << d << '\n';
    EXPECT_THROW(dijkstra.solve(g, 100, -1), std::logic_error);
    std::cout << g << '\n';
    d = -1;
    path = dijkstra.solve(g, -1, 7, &d);
    for (auto const& p : path) {
        std::cout << p << '\n';
    }
    std::cout << "d: " << d << '\n';
    //
    d = -1;
    path = dijkstra.solve(g, -1, -1, &d);
    for (auto const& p : path) {
        std::cout << p << '\n';
    }
    std::cout << "d: " << d << '\n';
    //
    d = -1;
    path = dijkstra.solve(g, 7, 7, &d);
    for (auto const& p : path) {
        std::cout << p << '\n';
    }
    std::cout << "d: " << d << '\n';
    //
    EXPECT_TRUE(g.hasVertex(0));
    EXPECT_TRUE(g.hasEdge(0, -1));
    //
    EXPECT_TRUE(g.hasVertex(3));
    EXPECT_TRUE(g.hasEdge(3, 100));
    EXPECT_TRUE(g.removeEdge(3, 100));
    EXPECT_FALSE(g.hasEdge(3, 100));
    std::cout << g << '\n';
    EXPECT_TRUE(g.removeVertex(3));
    EXPECT_FALSE(g.hasVertex(3));
    std::cout << g << '\n';
    g.clear();
    std::cout << g << '\n';
}
TEST(Dijkstra, solve_2)
{
    DijkstraGraph<char, double> g0;
    EXPECT_FALSE(g0.hasVertex(0));
    EXPECT_FALSE(g0.hasVertex('B'));
    EXPECT_FALSE(g0.hasVertex('s'));
    EXPECT_FALSE(g0.hasEdge(0, 'B'));
    EXPECT_FALSE(g0.hasEdge(0, 's'));
    //
    DijkstraSd dij;
    DijkstraGraph<std::string, double> g;
    EXPECT_THROW(dij.solve(g, "aaa", "bbb"), std::logic_error);
    //
    g.addVertex("aaa", "z", 100);
    g.addVertex("aaa", "x", 100);
    g.addVertex("z", "bbb", 200);
    g.addVertex("x", "bbb", 10);
    g.addVertex("bbb", "z", 1000);
    std::cout << g << '\n';
    EXPECT_EQ(4u, g.getSize());
    double d = -1;
    auto path = dij.solve(g, "aaa", "bbb", &d);
    for (auto const& p : path) {
        std::cout << p << '\n';
    }
    std::cout << "d: " << d << '\n';
    EXPECT_EQ((std::vector<std::string>{ "aaa", "x", "bbb" }), path);
}
$ ./test/dijkstra.test
[==========] Running 2 tests from 1 test case.
[----------] Global test environment set-up.
[----------] 2 tests from Dijkstra
[ RUN      ] Dijkstra.solve
-1
3
100
d: 31.23
(6) 7->7:0;; 5->7:2;; 0->3:200;0->-1:3.3;; -1->3:20;; 100->3:10;; 3->5:-10;3->100:11.23;;
-1
3
5
7
d: 12
-1
d: 0
7
d: 0
(6) 7->7:0;; 5->7:2;; 0->3:200;0->-1:3.3;; -1->3:20;; 100->3:10;; 3->5:-10;;
(5) 7->7:0;; 5->7:2;; 0->3:200;0->-1:3.3;; -1->3:20;; 100->3:10;;
(0)
[       OK ] Dijkstra.solve (1 ms)
[ RUN      ] Dijkstra.solve_2
(4) x->bbb:10;; bbb->z:1000;; z->bbb:200;; aaa->x:100;aaa->z:100;;
aaa
x
bbb
d: 110
[       OK ] Dijkstra.solve_2 (0 ms)
[----------] 2 tests from Dijkstra (1 ms total)

[----------] Global test environment tear-down
[==========] 2 tests from 1 test cas

See also