0

I have been experimenting with implementing Dijkstra's algorithm in C++ and used this pseudocode from wikipedia as a start:

 1  function Dijkstra(Graph, source):
 2      
 3      for each vertex v in Graph.Vertices:
 4          dist[v] ← INFINITY
 5          prev[v] ← UNDEFINED
 6          add v to Q
 7      dist[source] ← 0
 8      
 9      while Q is not empty:
10          u ← vertex in Q with min dist[u]
11          remove u from Q
12          
13          for each neighbor v of u still in Q:
14              alt ← dist[u] + Graph.Edges(u, v)
15              if alt < dist[v] and dist[u] is not INFINITY:
16                  dist[v] ← alt
17                  prev[v] ← u
18
19      return dist[], prev[]

While also using this tutorial and the C++ code as a template/help: https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/.

I have since then tried to expand the code to not just find the distance from source to each vertex, but instead just trying to find the shortest path from source to a target. Tried this by implementing pseudocode from wikipedia for that:

If we are only interested in a shortest path between vertices source and target, we can terminate the search after line 10 if u = target. Now we can read the shortest path from source to target by reverse iteration:

1  S ← empty sequence
2  u ← target
3  if prev[u] is defined or u = source:          // Do something only if the vertex is reachable
4      while u is defined:                       // Construct the shortest path with a stack S
5          insert u at the beginning of S        // Push the vertex onto the stack
6          u ← prev[u]                           // Traverse from target to sourc

This is my current code:

#include <iostream>
#include <vector>
using namespace std;
#include <limits.h>

#define V 9

int minDistance(int dist[], bool prev[])
{
    // Initialize min value
    int min = INT_MAX, min_index;
 
    for (int v = 0; v < V; v++)
        if (prev[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
 
    return min_index;
}

void printSolution(int dist[])
{
    cout <<"Vertex \t Distance from Source" << endl;
    for (int i = 0; i < V; i++)
        cout  << i << " \t\t"<<dist[i]<< endl;
}

void dijkstra(int graph[V][V], int src, int target) {
    
    int dist[V];
    int prev[V];
    bool Q[V];
    //bool true_target = false;
    int S[V];

    for (int i=0; i < V; i++) {
        dist[i] = INT_MAX;
        prev[i] = INT_MAX;
        // add v to Q
        Q[i] = false;
    }
    dist[src] = 0;

    //while Q is not empty:
    for (int count = 0; count < V-1; count++) {
        int u = minDistance(dist, Q);
        cout << "u: " << u << endl;
        vector<int> S;
        //true_target = (u==target);
        if (u == target) {
            if ((prev[u] != INT_MAX) || (u = src)) {
                while(u > 0) {
                    cout << u << endl;
                    S.push_back(u);
                    u = prev[u];
                }
                cout << "END" << endl;
                for (auto j = S.begin(); j != S.end(); ++j) {
                    cout << *j << ' ';
                }
                return;
            }
        }
        Q[u] = true;

        for (int v = 0; v < V; v++) {
            //cout << graph[u][v] << endl;
            if (!Q[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                prev[v] = u;
            }
        }
    }

    printSolution(dist);
}

int main ()
 {

     int graph[V][V] = {{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, 14, 10, 0, 2, 0, 0},
                        {0, 0, 0, 0, 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, 4);

     return 0;
 }

My main problem is that vertex 4, the vertex farthest away from the source, is not a vertex my current code can find a path to. When trying to find a path to 4 the output is:

u: 0
u: 1
u: 7
u: 6
u: 5
u: 2
u: 8
u: 3
Vertex   Distance from Source
0               0
1               4
2               12
3               19
4               21
5               11
6               9
7               8
8               14

Showing that an u: 4 is never generated, unlike trying to find a path to 5:

u: 0
u: 1
u: 7
u: 6
u: 5
5
6
7
END
5 6 7

That find u: 5 and shows a path back to source.

Appreciate any help. Thanks ^^

OverDemon
  • 103
  • 1
  • 3
  • 8
  • 1
    That GFG site is notorious for bad code, bad examples, and bad explanations. It's too bad that so many new C++ programmers go there to learn C++. The second thing is this -- [debug your code](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) -- use a debugger to see where the code you wrote diverges from the plan you wrote on paper. – PaulMcKenzie Aug 11 '22 at 08:20
  • I would not write code like that, at no place in your code the size of the passed arrays can be checked. Have a look at `std::vector` or `std::array` for passing arrays (preferably const&) – Pepijn Kramer Aug 11 '22 at 09:30

0 Answers0