Shortest path Dijkstra's algorithm

Question

I'm trying to implement Dijkstra's algorithm to find the shortest path from a starting node to the last node of a 250px by 200px raw image file (e.g. starting node = [0][0], ending node = [250][200]). The raw file acts like a topographical map in that each byte represents an elevation and the distance cost from one node to its adjacent node(s) is the difference in elevations of the two nodes plus 1 for the energy to move from one node to its neighbor (movement can only happen horizontally and vertically).

I have followed the pseudocode for the algorithm using a priority queue in C++, but am struggling to debug to see if I have successfully implemented the algorithm correctly as well as implementing the algorithm to accomplish this unique and relatively challenging situation. Also, my goal is to output the shortest path in a raw file and then view it in Photoshop to see if it is being displayed correctly, but have failed completely at this task.

After all that, my questions are:

1. Are there any visible/blaring logical errors in my implementation of solving the above described problem?
2. Could anyone suggest some ideas on how to try to output the shortest path in a raw file or something along similar lines?

I know I've used file read and write operations with the C notation rather than the stream operations of C++ so there's no need of telling me how I can change that.

#include <iostream>
#include <fstream>
#include <iomanip>
#include <queue>

#define INFINITY 99999
#define MAP_SIZE 50000  // 250px by 200px


void dijkstra(int, int, unsigned int []);

// The terminology 'Node' and 'Vertex' are used interchangeably
// throughout the program.
struct Node
{
    int index;              // index of node in graph
    unsigned int distance;  // distance from source (only allow positive distances)
};

// A simple class to compare the distances of two Node structures.
class CompareDist
{
public:
    bool operator()(Node& n1, Node& n2)
    {
        if (n1.distance < n2.distance)
            return true;
        else
            return false;
    }
};


int main()
{
    FILE *fr = fopen("map.raw","rb");
    FILE *fw1 = fopen("path.raw","w+");

    int i;
    unsigned char read[MAP_SIZE];
    unsigned int original[MAP_SIZE];    //2D array implemented in 1D array
    unsigned char path[MAP_SIZE];


    if(!fr){
        std::cout<<"Error: Can't open raw file!"<<std::endl;
        return 0;
    }
    fread(read, sizeof(char), MAP_SIZE, fr);
    fclose(fr);

    //convert to int for calculation
    for (i = 0; i < MAP_SIZE; i++) {
        original[i] = (int)((unsigned short)read[i]);
    }


    dijkstra(0, MAP_SIZE, original);


    for (i = 0; i < MAP_SIZE; i++) {
        path[i] = (unsigned char)original[i]; // output path array
    }

    fwrite(&path,sizeof(char),MAP_SIZE,fw1);

    fclose(fw1);


    return 0;
}

// Implementation of dijkstra's algorithm using a priority queue
// Inputs: int s --> source node
//         int size --> the total number of vertices in graph
//         unsigned int graph[] --> your graph
// Outputs: nothing
void dijkstra(int source, int size, unsigned int graph[MAP_SIZE])
{
    bool *visited = new bool [size];                    // array to check which vertices have already been visited
    unsigned int *distance = new unsigned int [size];   // table to hold the distances of each vertex from the source vertex

    // initialize the distance of each node to infinity and visited as false
    for (int i = 0; i < size; i++)
    {
        distance[i] = INFINITY;
        visited[i] = false;
    }

    // the distance of the source to itself is obviously 0
    distance[source] = 0;

    // create priority queue structure
    std::priority_queue< Node, std::vector< Node >, CompareDist> priorityQ;

    // Create the first node as the source and put it into the queue
    Node first = { source, 0 };
    priorityQ.push(first);

    // Pick the top node of priority queue.
    // Update the queue with next visited vertex after checking
    // which non-visited vertex has the minimum distance from
    // the source vertex.
    while(!priorityQ.empty())
    {
        Node tempNode = priorityQ.top();
        priorityQ.pop();
        int nodeIndex = tempNode.index;

        visited[nodeIndex] = true;
        for(int i = 0;i < size; i++)
        {
            if(graph[i] != 0 && !visited[i])
            {
                // Update the distance if it is smaller than the current distance
                int tempDist = distance[nodeIndex] + graph[i] + 1;
                if(distance[i] > tempDist)
                {
                    distance[i] = tempDist;
                    Node newNode;
                    newNode.index = i;
                    newNode.distance = distance[i];
                    priorityQ.push(newNode);
                }
            }
        }
    }

    // DEBUG TEST FOR CORRECT OUTPUT
    std::cout << "The shortest distance from " << source << " to all other nodes is" << std::endl;
    for(int i = 0; i < size; i++)
    {
        std::cout << i << " : " << distance[i] << std::endl;
        graph[i] = distance [i];
    }
    std::cout << std::endl << std::endl;
}

Answer 1

There's a few things I would suggest here that could make your code more idiomatic c++.

#define INFINITY 99999
#define MAP_SIZE 50000  // 250px by 200px

First off I'd make these const ints:

const unsigned int INFINITY = 99999; //more about this choice of data type later
const int MAP_SIZE = 250 * 200;

This way you now have named variables that have types. This can solve some problems immediately when you get type conversions that you didn't intend or want and it can help if you are debugging your code in a debugger.

The next thing is that I would change INFINITY to be the largest value that can possibly be represented in that type:

#include<limits>
const int INFINITY = std::numeric_limits<unsigned int>::max();

Now that INFINITY is the largest value that can be stored in an unsigned int you won't ever have x > INFINITY evaluate to true if x is an unsigned int. This can potentially prevent some subtle bugs, later on when you initialize your distance you are using this value and seeing as distance was storing an array of unsigned ints you want infinity to be the same type. (Compile with -Wconversion and you might see warnings from doing comparisons with signed vs unsigned, take those warnings seriously too.)

Your comparison class (I would make it a struct but that's probably a minor point) seems mostly fine, but I would change the comparison to take const references.

struct CompareDist
{
    bool operator()(Node const& n1, Node const& n2)
    {
        return (n1.distance < n2.distance);
    }
};

You also can just return the result directly and skip the if-else block entirely as it's completely redundant.

unsigned char read[MAP_SIZE];
unsigned int original[MAP_SIZE];    //2D array implemented in 1D array
unsigned char path[MAP_SIZE];

For all these I would use the newer std::array classes along with a typedef for convenience.

typedef std::array<unsigned int, MAP_SIZE> graph_array_t;
typedef std::array<unsigned char, MAP_SIZE> graph_path_array_t;

graph_array_t original;    //2D array implemented in 1D array
graph_path_array_t path;
graph_path_array_t read;

The std::array doesn't have some of the pitfalls of the raw arrays, works better with STL algorithms and doesn't cost you any performance hit.

I would change a few things with the first loop in main:

for (int i = 0; i < MAP_SIZE; i++) {
    original[i] = static_cast<unsigned int>(read[i]);
}

You'll see the scope of i is now reduced just to that for loop. If you try to reuse the loop variable later you will now get a compiler warning or error. I also removed one of the casts, it's fairly dubious to be making 2 casts in a row, if changing this to one cast breaks the code you really need to comment and explain why. If you are doing that because you need a particular width for your integers you should make a comment about that and explicitly specify the width in bits that you want by using the specific data types like uint8_t uint16_t as these will be guaranteed to work across different platforms. Also I've used the newer c++ cast syntax because it's easier to search for and specifies the exact type of cast you wish to perform.

Given the change of the data type for the graph the function parameters now have to change:

void dijkstra(int source, int size, graph_array_t const& graph)

In that function you have pointers to primitive data types, just store those types by value. You only really want to go to the extra effort of storing pointers to the data if the data is bigger than a pointer representing that data.

bool *visited = new bool [size];                    // array to check which vertices have already been visited
unsigned int *distance = new unsigned int [size];   // table to hold the distances of each vertex from the source vertex

So I'd use a std::vector to store these by value like so:

std::vector<bool> visited(size);
std::vector<unsigned int> distance(size);