Need a solution with this Dijkstra Algorithm

[Aldo33]

Hello guys i really need help to complile my program due today midnight. It want Write a program, which computes the shortest paths in a graph. Given the graph description
the program should compute the shortest path from vertex 1 to vertex n.

It reads form an input file that look like this:
7 12 //7 vertices and 12 edges
1 2 6 //edge between vertex 1 and vertex 2 has length 6
1 3 4 //edge between vertex 1 and vertex 3 has length 4
1 5 1 //etc.
2 3 1
3 5 2
2 4 3
5 6 4
3 4 5
3 6 1
3 7 5
6 7 7
4 7 1

And the output should be something like this:
8 //shortest path from vertex 1 to vertex 7 has a total length 8
1 5 3 2 4 7 //path 1→ 5→ 3→ 2→ 4→ 7.

And I really dont know how to do this i really appreciate if someone helps me even if he cant with text file but with just normal input form the console like this order.


I have me this code but it print me the wrong answer :(

#include <fstream>
#include <functional>
#include <climits>
#include <vector>
#include <queue>
#include <list>

using namespace std;

struct node {
int vertex;
int weight;
node(int v, int w) : vertex(v), weight(w) { };
node() { }
};

class CompareGreater {
public:
bool const operator()(node &nodeX, node &nodeY) {
return (nodeX.weight > nodeY.weight) ;
}
};

vector< list<node> > adj;
vector<int> weights;
priority_queue<node, vector<node>, CompareGreater> Q;

int nrVertices, nrEdges;

void readData();
void Dijkstra(node);
void writeData();

int main(int argc, char *argv[]) {

readData();
Dijkstra(node(1, 0));
writeData();

return 0;
}

void readData() {
fstream in("in10.txt", ios::in);

int nodeX, nodeY, weight;

in >> nrVertices >> nrEdges;

adj.resize(nrVertices+1);
weights.resize(nrVertices+1);

for (int i = 1; i <= nrVertices; ++i) {
weights.at(i) = INT_MAX;
}

for (int i = 1; i <= nrEdges; ++i) {
in >> nodeX >> nodeY >> weight;
adj[nodeX].push_back(node(nodeY, weight));
}

in.close();
}

void Dijkstra(node startNode) {
node currentNode;

weights[startNode.vertex] = 0;
Q.push(startNode);

while (!Q.empty()) {
currentNode = Q.top();
Q.pop();

if (currentNode.weight <= weights[currentNode.vertex]) {
for (list<node>::iterator it = adj[currentNode.vertex].begin(); it != adj[currentNode.vertex].end(); ++it) {
if (weights[it->vertex] > weights[currentNode.vertex] + it->weight) {
weights[it->vertex] = weights[currentNode.vertex] + it->weight;
Q.push(node((it->vertex), weights[it->vertex]));
}
}
}
}
}

void writeData() {
fstream out("dijkstra.out", ios::out);

weights.resize(nrVertices+1);
for (vector<int>::iterator it = weights.begin()+1; it != weights.end(); ++it) {
out << (*it) << " ";
}

out.close();
}

[Aldo33]

Guys please no one knows how to solve this i really need a working solution.....

[Ganado]

Please, before anything else, edit your first post and add [code] and [/code] around your actual code, to format it.

I'm busy and don't have time right now to debug your program, but I'll just give you some general tips, and maybe another forum-goer can give more specific advice.

(1) Understand the problem logically, independent of the code.
Practice on paper. You have a graph in your file; I suggest physically drawing that graph on paper, and going through the algorithm yourself, step by step, to figure out why the correct answer is, in fact, correct.

(2) Break the problem down into parts that you can verify for correctness.
You say that the end result is not correct. But there's a lot of that happens between the start of your program and the end of it. Before you even perform Dijkstra's algorithm, are you sure the data in your graph structure is input correctly? Verify that your actual data structures look like how they should.

Figure out at which exact step your program's behavior starts to diverge from what your hand-done steps. Then figure out why it's doing different behavior.

There's also plenty of pseudo-code available on the internet, that you might be able to apply.
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

_______________________________________

PS: Your code is strikingly similar to http://www.cplusplus.com/forum/general/124853/
maybe read through that.

Also, this.
https://stackoverflow.com/questions/23401696/dijkstras-algorithm-with-adjacency-lists-and-priority-queue

[Aldo33]

I changed my code into something like this but it doesnt read from text file but anyway i dont want it, the problem now is that it print only the weight for the path but I also need to add a method which find the shortest path from vertex to target.....Can anyone help me with that

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

#define MAX 100001
#define INF (1<<20)
#define pii pair< int, int >
#define pb(x) push_back(x)

struct comp {
bool operator() (const pii &a, const pii &b) {
return a.second > b.second;
}
};

priority_queue< pii, vector< pii >, comp > Q;
vector< pii > G[MAX];
int D[MAX];
bool F[MAX];

int main() {
int i, u, v, w, sz, nodes, edges, starting;

// create graph
scanf("%d %d", &nodes, &edges);
for(i=0; i<edges; i++) {
scanf("%d %d %d", &u, &v, &w);
G[u].pb(pii(v, w));
G[v].pb(pii(u, w)); // for undirected
}
scanf("%d", &starting);

// initialize distance vector
for(i=1; i<=nodes; i++) D[i] = INF;
D[starting] = 0;
Q.push(pii(starting, 0));

// dijkstra
while(!Q.empty()) {
u = Q.top().first;
Q.pop();
if(F[u]) continue;
sz = G[u].size();
for(i=0; i<sz; i++) {
v = G[u][i].first;
w = G[u][i].second;
if(!F[v] && D[u]+w < D[v]) {
D[v] = D[u] + w;
Q.push(pii(v, D[v]));
}
}
F[u] = 1; // done with u
}

// result
for(i=1; i<=nodes; i++) printf("Node %d, min weight = %d\n", i, D[i]);
return 0;
}