Dijkstra's Algorithm C++

Question

This is a basic implementation of Dijkstra's Shortest Path Algorithm for Graphs. I am looking for any kind of improvement.

/* 
    Author: Stevan Milic
    Date: 10.05.2018.
    Dijkstra's Shortest Path Algorithm
*/
#include <stdio.h> 
#include <limits.h> 
#include <iostream>

#define N 9 // Number of Nodes in the graph

int minDistance(int distance[], bool visitedSet[])
{
    int min = INT_MAX, min_index;

    for (int v = 0; v < N; v++)
        if (visitedSet[v] == false && distance[v] <= min)
            min = distance[v], min_index = v;
    return min_index;
}

void displayPath(int parent[], int s)
{
    if (parent[s] == -1)
        return;
    displayPath(parent, parent[s]);

    printf("-> %d ", s);
}

void display(int distance[], int n, int parent[])
{
    int start = 0;
    printf("Node\t     Distance\t         Path");
    for (int i = 1; i < N; i++)
    {
        printf("\n%d -> %d\t\t%d\t\t%d ", start, i, distance[i], start);
        displayPath(parent, i);
    }
}

void dijkstra(int graph[N][N], int start)
{
    int distance[N];

    bool visitedSet[N];

    int parent[N]; // For storing the shortest path tree

    for (int i = 0; i < N; i++) // This will make all distances as infinite and all nodes as unvisited
    {
        parent[0] = -1;
        distance[i] = INT_MAX;
        visitedSet[i] = false;
    }
    distance[start] = 0;
    for (int count = 0; count < N - 1; count++) // Finding the shortest path for all nodes
    {
        int u = minDistance(distance, visitedSet);

        visitedSet[u] = true;

        for (int n = 0; n < N; n++)
            if (!visitedSet[n] && graph[u][n] && distance[u] + graph[u][n] < distance[n])
            {
                parent[n] = u;
                distance[n] = distance[u] + graph[u][n];
            }
    }
    display(distance, N, parent);
}

int main()
{
    printf("***** Dijkstra's Shortest Path Algorithm ***** \n\n");
    int graph[N][N] = { {0, 4, 0, 0, 0, 0, 0, 8, 0 },
                        {4, 0, 8, 0, 0, 0, 0, 11, 0},
                        {0, 8, 0, 7, 0, 4, 0, 0, 2 },
                        {0, 0, 7, 0, 9, 14, 0, 0, 0},
                        {0, 0, 0, 9, 0, 10, 0, 0, 0},
                        {0, 0, 4, 0, 10, 0, 2, 0, 0},
                        {0, 0, 0, 14, 0, 2, 0, 1, 6},
                        {8, 11, 0, 0, 0, 0, 1, 0, 7},
                        {0, 0, 2, 0, 0, 0, 6, 7, 0 } 
                      };
    dijkstra(graph, 0);
    printf("\n\n");
    system("pause");
    return 0;
}

Answer 1

The <iostream> header is not used.

min_distance can theoretically return an uninitialized value if all elements of visited_set are nonzero. This shouldn't happen here, but initializing min_index = 0 would remove a potential problem and compiler warning.

display assumes that node 0 is the start node, but that value is passed in to dijkstra. It should be passed in as a parameter.

In dijkstra, the graph parameter could be const int graph[N][N], which would then allow the graph variable in main to also be const. The parent[0] = -1 assignment seems to be a typo. It should be parent[i] = -1; to initialize all elements of parent. The for (int n = 0; n < N; n++) loop should have curly brackets around its body. While not currently necessary, having them in can avoid future problems when the code is modified and makes it clearer what is in the loop body rather than looking like a line with bad indentation.

Answer 2

Overview

Terrible C++ but OK C.

Modern C++ has a completely different style when used to what you have written here. Though perfectly legal C++ this is not what you would expect to see and this makes it harder to maintain and implement.

Improvements

You tightly bind your interface to a specific implementation (an Array of Arrays of distance). You should abstract your design so that the algorithm can be applied to any type that matches the interface.

There are lots of standard types that would help you in this implementation. You should have a look to see what is useful

Efficiency

There are some definite improvements in efficiency that you can implement here. Your current algorithm is at least O(N^2) could be worse but I stopped looking. I would probably want it to be O(n.log(n)).

Code Review

These are C headers

#include <stdio.h> 
#include <limits.h> 

C++ has its own set of headers use them (cstdio and climits). They put all the functions correctly into the standard namespace (std::).

Don't include headers you don't need:

#include <iostream>

BUT you should need it.Prefer the C++ streams to the C io interface because of its type safety.

---

Avoid macros:

#define N 9 // Number of Nodes in the graph

All (most) the use of macros have better alternatives in C++. Macros should be reserved for what they are good at (identifying platform dependencies and providing the appropriate different functionalities for these platforms). Unless you are writing low level platform independent code you should not be touching these.

constepxr int N = 9;  // N is a terrible name (find a better one).

---

This is your main issue in complexity.

int minDistance(int distance[], bool visitedSet[])
{
    for (int v = 0; v < N; v++)   // Loop over all the nodes.
    ...
    return min_index;
}

You are doing a full sweep of all the nodes each time. If you had simply used a form of sorted list (as the algorithm tells you) then you reduce the overall complexity a lot.

---

Stop abusing the comma operator. It's not cool.

    int min = INT_MAX, min_index;       // Not technically the comma operator but same principle.

    min = distance[v], min_index = v;

The point of writing code in a high level language is so that it is easy for other humans to understand. By cramming everything on one line you are doing the exact opposite (making it hard to read and therefore understand and therefore maintain).

Every coding standard I have ever read is one variable modification per line. One declaration per line. It does not hurt to use an extra line here.

---

Prefer to always put sub blocks inside '{}`

for (int v = 0; v < N; v++)
    if (visitedSet[v] == false && distance[v] <= min)
        min = distance[v], min_index = v;

Seriously: I mean seriously you think that make

for (int v = 0; v < N; v++) {
    if (visitedSet[v] == false && distance[v] <= min) {
        min = distance[v];
        min_index = v;
     }
}

Three extra lines. I mean I would add the { on their own lines (so 5) but you young people like to cram things together.

Your killing me:

    if (parent[s] == -1)
        return;

OK. I understand why you did (I was young once too). You saved a line and 5 character strokes. It looks safe. And in this case it is.

The trouble is that this is a bad habit that can (and will) get you into trouble. And when it does you will not spot that error for fucking days. The problem is that without the braces only one statement is valid as part of the sub block. But what happens if there is an extra statement hidden there that you can see?

 if (something)
     doStuff(data);

Looks innocent.

 #define doStuff(data)   doStuffStart(data);doStuffEnd(data)

Now you are fucked. And there are bad programmers out there so don't say people don't do that. They absolutely do and they will screw you one you least expect it. So be safe get in good habits and this will never burn you.

 if (something) {
     doStuff(data);
 }

---

Recursion is a nice tool:

void displayPath(int parent[], int s)
{
    displayPath(parent, parent[s]);
}

But it is dangerous and you can burn yourself. Prefer to use a loop if you can. Use recursion for trees where there is no other choice. I mean the compiler will also try and turn this into a loop for you. But because you added the print at the end tail recursion optimization can't kick in.

---

Sure that works:

    printf("***** Dijkstra's Shortest Path Algorithm ***** \n\n");
    printf("\n\n");

But filed under bad habit. Use the type safe C++ variants. Use of std::cout consistently means you can un bind the C++ streams from the C streams and gain impressive speed gains from the stream library. If you use both C and C++ versions you can unbind them as you will have buffering issues.

---

Why use platform specific code:

    system("pause");  // Also you are actually calling another program.

Much simpler and easier to do:

    std::cout << "Press Enter to exit\n";
    std::cin.ignore(numeric_limits<streamsize>::max(), '\n');

Now you have not created another separate processes just to check if you have hit enter.

---

Don't need this in C++

    return 0;

If there is no way to have an error then don't use it (the compiler will add the appropriate return 0 for you.

Normally people put this at the end as an indciation that somewhere else in main() there is a return 1 so when I see this I start looking for the error exit condition.

Dijkstra

// 1 You want a start and an end.
//   This way you can stop once you have found the best path from start to end
//   There could be thousands of nodes we don't even look at:
//
// 2 Abstract your graph representation from the implementation.
//   There are only a few methods you need to interrogate the graph.
//
// 3 The working list needs to be sorted by cost.
//   You can implement this in many ways but a good algorithm should 
//   probably only cost you log(n) to keep it sorted.
//   probably a lot less.
// 
// 4 The working set. You should be able to check it quickly.
//   std::set or std::hash_set would be good.
//
void dijkstra(Graph g, int Start, int End)
{
    WorkingSet  working;   // List of Node with cost sorted by cost.
    NodeSet     finished;  // List of nodes we have processed.

    working.addNode(Start, 0); // No cost to get to start.
    
    for( (node, cost) = working.popHead(); node != End; (node,cost) = working.popHead())
    {
        // If we have already processed this node ignore it.
        if (finished.find(node))
        {    continue;
        }
    
        // We have just removed a node from working.
        // Because it is the top of the list it is guaranteed to be the shortest route to
        // the node. If there is another route to the node it must go through one of the
        // other nodes in the working list which means the cost to reach it will be higher
        // (because working is sorted). Thus we have found the shortest route to the node.
    
        // As we have found the shortest route to the node save it in finished.
        finished.addNode(node,cost);
    
        // For each arc leading from this node we need to find where we can get to.
        foreach(arc in node.arcs())
        {
            dest = arc.dest();
            if (NOT (finished.find(dest)))
            {
                // If the node is already in finished then we don't need to worry about it
                // as that will be the shortest route other wise calculate the cost and add
                // this new node to the working list.
                destCost = arc.cost() + cost;
                working.addNode(dest,destCost); // Note. Working is sorted list
            }
        }
    } 
}

---

Starting point:

I have not tried this and it will probably take some tweaking.

 use NodeId      = int;
 use Cost        = int;
 use WorkingItem = std::pair<NodeId, Cost>;
 use Order       = [](WorkingItem const& lhs, WorkingItem const& rhs) {return lhs.second > rhs.second;};
 use WorkingSet  = std::priority_queue<WorkingItem, std::vector<WorkingItem>, Order>;

 use NodeSet     = std::set<NodeId>;