0
\$\begingroup\$

I am trying to implement the Dijkstra algorithm in C++ that finds the shortest path for a graph from a text file. The text file contains a matrix that represents a directed graph.

What I am trying to do in this code is use every vertex as the source. I finished the code but I am still very skeptical if my code is right or not.

int minDistance(int dist[], bool sptSet[], int V)
{
// Initialize min value
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)
    if (sptSet[v] == false && dist[v] <= min)
        min = dist[v], min_index = v;

return min_index;}
double  dijkstra(int vertex, int **graph, int src)
{
auto start_time = chrono::high_resolution_clock::now();
int* dist = new int[vertex];     // The output array.  dist[i] will hold the shortest
// distance from src to i

bool* sptSet = new bool[vertex]; // sptSet[i] will true if vertex i is included in shortest
// path tree or shortest distance from src to i is finalized


src = k;
// Initialize all distances as INFINITE and stpSet[] as false
for (int i = 0; i < vertex; i++)
    {
    dist[i] = INT_MAX, sptSet[i] = false;
    }

// Distance of source vertex from itself is always 0
dist[src] = 0;

// Find shortest path for all vertices
    for (int count = 0; count < vertex - 1; count++)
    {
    // Pick the minimum distance vertex from the set of vertices not
    // yet processed. u is always equal to src in first iteration.
    int u = minDistance(dist, sptSet, vertex);

    // Mark the picked vertex as processed
    sptSet[u] = true;

    // Update dist value of the adjacent vertices of the picked vertex.
    for (int v = 0; v < vertex; v++)

        // Update dist[v] only if is not in sptSet, there is an edge from 
        // u to v, and total weight of path from src to  v through u is 
        // smaller than current value of dist[v]
        if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
        {
        dist[v] = dist[u] + graph[u][v];
        }
    }
k++;
delete[] dist;
delete[] sptSet;
}


auto end_time = chrono::high_resolution_clock::now();
double elapsed = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();

return elapsed;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Have you run the code? Does it produce correct output? \$\endgroup\$ – Nick Udell Nov 5 '14 at 9:18
  • 1
    \$\begingroup\$ Your code is very poorly formatted, missing indentation in several spots. Was this a problem when posting the code here or is that how you wrote it? \$\endgroup\$ – glampert Nov 5 '14 at 16:51
3
\$\begingroup\$

I'm sure it'll be fairly easy for your to confirm if your code is working (you can find test cases all over the place), so I'm not looking to closely at correctness, so much as overall logic.

So, on the whole, it seems to make logical sense, but it's not an efficient implementation of Djikstra. As you know, Djikstra's algorithm involves having an ever increasing collection of nodes and picking the smallest path out of your collection (it's that simple).

The main flaw is in your minDistance() method. What you're doing there is effectively iterating over all the nodes you've selected and finding the shortest part out. That's an O(n) operation. This step in Djikstra is crucial and should be done in O(log N) time. This can be done using a set or a heap. Since you always want the minimum path out, all you need to do is keep track of the paths out and pick the min at each stage.

As I mentioned, you can do this with a set/heap. I think this example should help clear this up.

\$\endgroup\$
  • 2
    \$\begingroup\$ This AlgoList website is very interesting. Thanks for sharing that link! \$\endgroup\$ – glampert Nov 5 '14 at 16:52
  • \$\begingroup\$ The link ain't working! \$\endgroup\$ – CinCout Feb 20 '16 at 7:40
3
\$\begingroup\$

Not sure I believe that is Dijkstra's algorithm. I would expect to see two lists in the implementation: a list of reached nodes (have found shortest distance), and a sorted list of nodes that are the next to be searched.

It should look like this:

Dijkstra(Graph const& graph, Node start, Node end)
{
     List           reachedNodes;
     PriorityList   boundry;

     boundry.insert(start, 0, []);

     while(!boundry.empty())
     {
          nextNode,cost,route   = boundry.top();
          boundry.pop();

          if (nextNode == end)
          {
              // We found the route.
              route.append(end);
              return cost, route;
          }
          if (reachedNodes.find(nextNode) != reachedNodes.end())
          {
              // Already found best route to nextNode. So we can ignore it.
              continue;
          }
          // So this is the best route to nextNode :-)
          // We know this because `boundry` was sorted by lowest cost.
          // so add it to reached Nodes (we can ignore this node if we see it again).
          reachedNodes.insert(nextNode);

          // Add this node to the route.
          route.append(nextNode);

          // For each edge that comes out of this node.
          // Add it to the `boundry` with the new cost.
          foreach(edge: grpah.edgesFrom(nextNode))
          {
               boundry.insert(edge.dest, cost + edge.cost, route);
          }
     }
     // No route from start to end
     return infinity, [];
}
\$\endgroup\$
2
\$\begingroup\$

Improvement in code and programming style:

minDistance() takes two array parameters that are only read from. They should be qualified as const to document the intents of the function:

int minDistance(const int dist[], const bool sptSet[], int V);

Single letter names are OK in places like loop counters and array indexes, but not so much for function parameters. int V in minDistance() is not very descriptive. V is a vertex, the target of the search, I believe. Then name it as such: targetVertex.

Your code is very poorly indented. Not sure if that was a problem when you posted it here, if so, then disregard this comment. If not, then you have to pay a lot more attention to that. Properly indent code under each scope. As it stands right now, it is very difficult to read and reason about its flow of logic.

Manual memory management:

At the moment, you are manually allocating and freeing memory inside the dijkstra() function. There is little gain in doing that and it can lead to a ton of problems. If an exception is thrown in mid function, you have a memory leak. If you make the mistake of returning from the function without deallocating, there's a leak. Manually managing memory allocations inside function scope tend to generate complicated cleanup and error handling code. All this can be avoided by simply using a standard std::vector to automate the cleanup for you:

std::vector<int> dist(vertex);
std::vector<bool> sptSet(vertex);

// The delete[]s are no longer necessary.

Other style and architecture details:

Prefer using std::numeric_limits instead of the INT_MAX family of macros. The former is more modern.

You are currently computing the time the search took and returning it as the function's return value. This is an unusual setup. A more general function would not bother measuring its execution time, since this can easily be done at the call site before entering the function. If you have use cases where the caller doesn't care about the time taken, you are just wasting cycles computing that time delta.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.