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 ^^