Shortest path in image

This code takes an image and detects a global shortest path from the top to bottom row, with the requirement that top and bottom column index be the same. For this, it scans through each element on the top row using Dijkstra's algorithm towards its corresponding point on the bottom row. The shortest path is defined as the sum of all passed pixel values. The constraint here is that each pixel only has three neighbors in the next lower row; lower left, straight down, and lower right. This makes any expansion triangular. Each of those three neighborhood pixels gets the column index of the current pixel as a predecessor (we automatically know the predecessor row is one higher).

I ran a brute-force approach, calculating the shortest path by running along all rows and columns sequentially (pseudocode):

for every element (0,r) in the first row
   for rows i (1 : end)
       for cols j (r-i : r+i) //triangular expansion
          get distances of three elements in row above, so d (dist = infinite if not part of the triangular expansion)
          d[i,j] <- min(d[i-1,j-1],d[i-1,j],d[i-1,j+1]) + image[i,j]
          predecessor[i,j] <- column index of smallest of the three
   once final row is expanded get d[end,r]
   update global distance if d < previous global distance and corresponding global r
backtrack along predecessor matrix of smallest d starting from element (end, global r)

which takes about 3 seconds per image, while using Dijkstra's algorithm takes about 12 seconds:

```
#include "opencv2/imgproc/imgproc.hpp"
#include "opencv2/highgui/highgui.hpp"
#include "opencv2/opencv.hpp"
#include
#include
#include ///round
#include ///cout
#include
#include
#include

using namespace std;
using namespace cv;

const int inf = 0x7F800000;

struct Node
{
Point index; // index of node in graph
double distance; // distance from source (only allow positive distances)
};

struct CompareDist
{
bool operator()(Node const& n1, Node const& n

Style

Using using namespace std is bad. Same goes for using namespace cv obviously.

Your indentation is off, but I'm guessing that this is a copy paste error.

Comments

I find your comments to not be helpful. They should explain why something is done, not what is done. If you need comments to explain what you're doing, then you need to write clearer code with better variable and function names. Possibly breaking out more functions.

Combine definition and initialization

Code like this:

double upperLimit;
upperLimit = columnwiseSum.at(min_loc); // this is the first upper bound

has poor readability. You should structure it like this (again better name on variables):

double upperBound = columnwiseSum.at(min_loc);

See how I combined the definition and initialization of upperBound? This makes your code easier to follow, easier to verify that the variable is always initialized and also shorter to write.

There are multiple occasions of this.

Node class

The name index is wildly misleading, rather it's the position in the image. I would suggest renaming it to position. If you need to comment a member variable, its name is not good enough. Consider renaming distance to distanceFromSource.

Instead of providing the explicit comparator CompareDist you could simply provide an overload for operator > and use std::greater in your priority queue.

In summary:

struct Node
{
    Point position;
    double distanceFromSource;

    bool operator > (const Node& n) const{
        return distance > n.distance;
    }
};

...

std::priority_queue, std::greater>

But that's not infinite...

This really isn't infinity...

const int inf = 0x7F800000;

you are also assigning this to double when you want infinity:

double dist = inf; //global shortest path distance
double distTemp = inf; //shortest path distance for each dikstra run

you should just use: std::numeric_limits::infinity() and while you're at it, if you need to comment what a variable is, the name is bad. How about this:

double shortestPathDist = std::numeric_limits::infinity();
double shortestPathDistCurrent = std::numeric_limits::infinity();

Numerical inaccuracy

You are using float to accumulate the distances, after each floating point operation you introduce a truncation error on the order of x*E-6 where x is the stored value. If you'd simply use CV_32SC1 and image.at() you wouldn't have to worry about truncation errors affecting your graph search. You would probably also notice a speed up.

At any rate you're comparing floats to doubles and doing a lot of type-casting which is unnecessary and can take some time if done in a hot loop.

Mat initialisation

This:

// initialize the distance of each node to infinity
Mat distance = Mat::ones(image.size(),CV_32F);
multiply(distance,inf,distance);

going with the above advice to use numeric_limits should be:

Mat distance(image.size(), CV_32F);
distance = std::numeric_limits::infinity();

Dijkstra implementation

Okay the name pQueue tells me something about the type but not what it is used for. A much better name would be unvisitedNodes.

The variable first is only used once to push it into the pQueue better to just do it like this:

unvisitedNodes.emplace(source, image.at(source));

Always strive to reduce the number of variables, this makes it easier to reason about the state of the code (but not to absurdum ofcourse). Notice that this could be more readable if we renamed source to start which is more logical.

unvisitedNodes.emplace(start, image.at(start));

Now this tells me that I construct a new unvisited node from the start point. Great! Do note that dijkstra's algorithm starts with a '0' distance. But what you're doing is equivalent to starting at a node with only one edge, to the source node. So this won't affect your results.

The name tempNode again is a terrible name. Better names are currentNode or shortestPathNode.

Please do fix up your indentation:

Point nodeIndex = tempNode.index; // get element index 
if (nodeIndex == goal){ // found the path to goal
    return tempNode.distance;
    }

int newX, newY; //indices for neighborhood node
for(int i = -1; i < 2; i++) //for every neighborhood element 
    {
    newY = nodeIndex.y+1; //new row
    newX = nodeIndex.x+i; //new col

This is a proper nightmare to read. Again if you need to comment the variables, choose better names. Trust me, you'll save more time when you debug the code that you spend writing slightly longer names.

Instead of int newY, newX you should just have Point newPosition. Would simplify lots when addressing the images.

This:

```
// this constrains the expansion within a diamond shape, since only certain neighboring nodes are allowed
if (newY = source.x-newY && newX floor(image.rows/2) && (newX >=source.x-(goal.y-newY) && newX <=source.x+(goal.y-newY))))

StackExchange Code Review Q#99035, answer score: 2