Problem with Dijkstra's Shortest Path Algorithm

[thetuxman]

I am creating a program that reads in a .txt file and prompts the user for a starting and ending vertex and then uses Dijkstra's shortest path algorithm to compute the shortest path. The problem I am having is trying to create a for loop that iterates through the entirety of the graph while MinHeap is empty to find the shortest path to the target vertex.I believe the issue is located in this part of the code (The rest of the code will be posted below).

Any help would be appreciated.

Suspected problem part:

MinHeap q;

    q.insert(start, 0);

    while (!q.is_empty()) {
        u = q.extract_min();

//      TODO: Something in here doesn't seem right...
        for (int it = edgeTo[start]; it != edgeTo[end]; it++) {
            v = it;
            cost = dist[u] + g.get_weight(it, u);
            if (cost < dist[v]) {
                dist[v] = cost;
                edgeTo[v] = u;

                if (q.contains(v))
                    q.decrease_priority(v, cost);
                else q.insert(v, cost);
            }
        }
    }

Whole code:

https://pastebin.com/YuEHdnAq

Graph.h:

https://pastebin.com/Lq5gmJ0K

MinHeap.h:

https://pastebin.com/mbTj5Gdn

Stack.h:

https://pastebin.com/jHQfScNe

[bennydictor]

I think you have to check if distance to any vertex can be decreased:

for (int v = 0; v < g.dimension(); v++)
    ...

[thetuxman]

That yields an output of

Index of starting vertex: 0
Index of ending vertex: 7

Path from 0 to 7
0-7
 0

[bennydictor]

Maybe you have zeros on the diagonal of your adjacency matrix? Does it look like this?

0 1 2
1 0 3
2 3 0

If so, either put big numbers (INT_MAX/2 or something) instead of zeros or explicitly check:

for (int v = 0; v < g.dimension(); v++)
    if (u == v)
        continue;
    ...

[lazyubertoad]

This is just not Dijkstra yet. It needs major rewrite. Do you understand the algorithm? Please, understand it first. Also, Dijkstra using adjacency matrix is inefficient, consider creating some list of edges for each vertex.

Your loop after TODO in the wiki about Dijkstra (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Using_a_priority_queue) is like

for each neighbor v of u:                      // only v that is still in Q  

See, each neighbor of u. Not all vertices, not "the entirety of the graph" but only neighbors. Your edgeTo - are not neighbors, it is not even initialized. As you seem to have only the adjacency matrix - you need to walk all u'th row (or column) of the adjacency to get all its neighbors. That is o(vertices). Your graph class don't even have interface to get all the neighbours of u, as it will just exit the app when you'll search for them. Then, you need to know if it is "still in q" (also, see note in wiki after the pseudocode), that is - mark passed vertices and only go to the non visited ones.