12 Replies - 957 Views - Last Post: 02 December 2016 - 06:17 PM Rate Topic: -----

#1 brandon236   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 04-December 15

What's wrong with my Dijkstra's algorithm implementation?

Posted 30 November 2016 - 10:15 AM

So I'm trying to implement Dijkstra's algorithm in Java. I know there are different ways to do it but here's the way that I've learned to do it. So I start with a single vertex and I find the shortest path from that vertex to every other vertex. I start with a single vertex (in my case it's zero) and then update my neighborhood by relaxing all the edges connected to that vertex. I then find out what's the smallest edge that connects to the current edge and then I add that vertex to my vertex storage. I keep doing that until all the vertices are in my vertex storage and then I should end up with a type of spanning tree that shows me all the shortest paths.

So in my code, I'm trying to find the shortest path from 0 to 1. I get the graphs from an adjacency matrix. So what I do is I start at the first row (or the 0th row) and traverse through the row and relax the vertices in a matrix called N. I then find the smallest edge coming out of whatever vertices I have stored in my vertex storage and then continue adding vertices and relaxing the edges. So then I have two main arrays called N (where I store the weights of the shortest paths) and edgeStorage. Here's what it looks like:
static int ShortestPath(int[][] G){
    int numVerts = G.length;
    int totalWeight = 0;

    int minWeight;
    int count = 1;
    int k = 0;
    int l = 0;
    int next = 1;
    int i = 0;
    int[] N = new int[numVerts];
    int[] edgeStorage = new int[numVerts];
    Arrays.fill(N, 2147483647); //2147483647 is my infinity to represent vertices that haven't yet been relaxed
    N[0] = 0;

    while (count != numVerts){
        for (int j = 0; j < numVerts; j++){
            if ((G[i][j] != 0) && (N[i] + G[i][j] < N[j])){
                N[j] = N[i] + G[i][j];
            }
        }
        minWeight = 2147483647;
        for (int p = 0; p < count; p++){ //find min edge weight for vertices in storage
            i = edgeStorage[p];
            for (int j = 0; j < numVerts; j++){
                if ((G[i][j] != 0) && (G[i][j] < minWeight)){
                    minWeight = G[i][j];
                    k = j;
                    l = i;
                }
            }
        }
        G[l][k] = 0; //remove edge since we don't need it anymore
        G[k][l] = 0;
        edgeStorage[next] = k; //store vertex location in array
        i = k;
        count++;
        next++;
    }
    totalWeight = N[1];
    return totalWeight;
}


The problem is this code works for some graphs but for others it gives me a weight that's bigger than it's supposed to be. I have no idea why it gives me the wrong weight for some graphs but the right weight for others. So does anyone know what's wrong with my code?

Is This A Good Question/Topic? 0
  • +

Replies To: What's wrong with my Dijkstra's algorithm implementation?

#2 NormR   User is offline

  • D.I.C Lover
  • member icon

Reputation: 797
  • View blog
  • Posts: 6,062
  • Joined: 25-December 13

Re: What's wrong with my Dijkstra's algorithm implementation?

Posted 30 November 2016 - 11:36 AM

Quote

code works for some graphs but for others it gives me a weight that's bigger than it's supposed to be

How are you trying to debug the code?
For the graphs where the code does not work as desired, do you know how the algorithm should work to solve the problem? If you printed out the steps the program takes, that print out should help you find where the code is going wrong.
Was This Post Helpful? 0
  • +
  • -

#3 brandon236   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 04-December 15

Re: What's wrong with my Dijkstra's algorithm implementation?

Posted 01 December 2016 - 02:39 PM

View PostNormR, on 30 November 2016 - 11:36 AM, said:

Quote

code works for some graphs but for others it gives me a weight that's bigger than it's supposed to be

How are you trying to debug the code?
For the graphs where the code does not work as desired, do you know how the algorithm should work to solve the problem? If you printed out the steps the program takes, that print out should help you find where the code is going wrong.

The problem is all the 10 vertex graphs work fine. It's just the 25 vertex graphs that don't work and I'm also using adjacency matrices so I would have to convert the matrix to a graph of 25 vertices and then do dijkstra's algorithm by hand and I don't know how that would work out.
Was This Post Helpful? 0
  • +
  • -

#4 NormR   User is offline

  • D.I.C Lover
  • member icon

Reputation: 797
  • View blog
  • Posts: 6,062
  • Joined: 25-December 13

Re: What's wrong with my Dijkstra's algorithm implementation?

Posted 01 December 2016 - 03:06 PM

I can only suggest working out a solution by hand and then tracing the code to see where it goes wrong.
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,864
  • Joined: 27-December 08

Re: What's wrong with my Dijkstra's algorithm implementation?

Posted 01 December 2016 - 03:56 PM

One thing to note is that the edges should be stored in a priority queue. Managing an array and enforcing the priority queue structure yourself leaves you open for careless errors. Glancing through your code, I suspect this may be contributing to the issue. You should either roll a PriorityQueue class or use the built in java.util.PriorityQueue.

Another point is that it is cleaner to treat edges as objects, rather than x, y points in a matrix. OOP is your friend here. This leads me into my final point that an adjacency matrix is incredibly redundant compared to an incidence list representation. You are storing edges twice, as well as non-edges twice, which results in n^2 memory just for the graph and lots of redundant checks/operations.

If you have a specific, reasonably sized graph, we're happy to help you trace through that. If you can narrow down the issues, we're happy to help there too. However, right now your issue is too vague for us to be of much more assistance.
Was This Post Helpful? 0
  • +
  • -

#6 brandon236   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 04-December 15

Re: What's wrong with my Dijkstra's algorithm implementation?

Posted 01 December 2016 - 09:02 PM

View Postmacosxnerd101, on 01 December 2016 - 03:56 PM, said:

One thing to note is that the edges should be stored in a priority queue. Managing an array and enforcing the priority queue structure yourself leaves you open for careless errors. Glancing through your code, I suspect this may be contributing to the issue. You should either roll a PriorityQueue class or use the built in java.util.PriorityQueue.

Another point is that it is cleaner to treat edges as objects, rather than x, y points in a matrix. OOP is your friend here. This leads me into my final point that an adjacency matrix is incredibly redundant compared to an incidence list representation. You are storing edges twice, as well as non-edges twice, which results in n^2 memory just for the graph and lots of redundant checks/operations.

If you have a specific, reasonably sized graph, we're happy to help you trace through that. If you can narrow down the issues, we're happy to help there too. However, right now your issue is too vague for us to be of much more assistance.

I was planning on storing the edges in a priority queue. I just wanted to start out with a simpler method however if the problem really is the fact that the edges should be stored in a priority queue then I can try that. I also already traced through the code with the adjacency matrix and the answer I got was the same answer my code was outputting (the wrong answer). It's almost as if the code is doing exactly what I want it to do but what I want it to do isn't right. An easy way to tell what is going wrong is to draw out the tree that corresponds to the incorrect matrix however the smallest incorrect matrix is 25 vertices which is quite difficult to draw out.

As for adjacency matrices, I know that there are ways to make the run time faster however I actually have to use adjacency matrices right now. So I have to work with adjacency matrices for this code and get the run time to be O(n2 + mlogn).
Was This Post Helpful? 0
  • +
  • -

#7 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,864
  • Joined: 27-December 08

Re: What's wrong with my Dijkstra's algorithm implementation?

Posted 01 December 2016 - 10:40 PM

Quote

I just wanted to start out with a simpler method however if the problem really is the fact that the edges should be stored in a priority queue then I can try that. I also already traced through the code with the adjacency matrix and the answer I got was the same answer my code was outputting (the wrong answer).

Your approach of omitting a priority queue is not simpler. A key component of software engineering is to (re)use existing components. Delegating to a priority queue is less work on you, and less room for mistakes.
Was This Post Helpful? 0
  • +
  • -

#8 brandon236   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 04-December 15

Re: What's wrong with my Dijkstra's algorithm implementation?

Posted 02 December 2016 - 12:01 AM

View Postmacosxnerd101, on 01 December 2016 - 10:40 PM, said:

Quote

I just wanted to start out with a simpler method however if the problem really is the fact that the edges should be stored in a priority queue then I can try that. I also already traced through the code with the adjacency matrix and the answer I got was the same answer my code was outputting (the wrong answer).

Your approach of omitting a priority queue is not simpler. A key component of software engineering is to (re)use existing components. Delegating to a priority queue is less work on you, and less room for mistakes.

Ok so how do I implement a priority queue? I've done import
java.util.PriorityQueue;
and I've declared the priority queue like this
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(numVerts);
so then how can I use that to implement dijkstra's?
Was This Post Helpful? 0
  • +
  • -

#9 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,864
  • Joined: 27-December 08

Re: What's wrong with my Dijkstra's algorithm implementation?

Posted 02 December 2016 - 07:07 AM

An edge isn't an integer. What information does a weighted edge store?

Also- look at Dijkstra'a algorithm more closely. Once you do that, can you tell me where the PriotityQueue is used?
Was This Post Helpful? 0
  • +
  • -

#10 brandon236   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 04-December 15

Re: What's wrong with my Dijkstra's algorithm implementation?

Posted 02 December 2016 - 10:13 AM

View Postmacosxnerd101, on 02 December 2016 - 07:07 AM, said:

An edge isn't an integer. What information does a weighted edge store?

Also- look at Dijkstra'a algorithm more closely. Once you do that, can you tell me where the PriotityQueue is used?

It looks like it would be used to find the min edge since it would be a heap based priority queue. I assume with you add a vertex into the cloud of vertices then every vertex coming out of the cloud would be added to the priority queue and the edge in the front of the queue will be the smallest.
Was This Post Helpful? 0
  • +
  • -

#11 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,864
  • Joined: 27-December 08

Re: What's wrong with my Dijkstra's algorithm implementation?

Posted 02 December 2016 - 11:26 AM

The data structure supporting the priority queue is important for issues of complexity, but not of correctness. The priority queue returns the smallest weight edge, which is what you want.

Note that you add unvisited edges, not vertices, to the priority queue.
Was This Post Helpful? 0
  • +
  • -

#12 brandon236   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 04-December 15

Re: What's wrong with my Dijkstra's algorithm implementation?

Posted 02 December 2016 - 12:14 PM

View Postmacosxnerd101, on 02 December 2016 - 11:26 AM, said:

The data structure supporting the priority queue is important for issues of complexity, but not of correctness. The priority queue returns the smallest weight edge, which is what you want.

Note that you add unvisited edges, not vertices, to the priority queue.

Ok so then with each vertex, I find all the edges connected to that vertex and then the smallest edge will always be at the front of the pq. Then when I find the smallest edge I remove it from the queue. The only thing I'm wondering is how do I set up a priority queue? I currently have
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(numVerts);
because that's the only one that works. If I put something besides Integer in the brackets, I get an error that says they couldn't find the symbol.
Was This Post Helpful? 0
  • +
  • -

#13 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,864
  • Joined: 27-December 08

Re: What's wrong with my Dijkstra's algorithm implementation?

Posted 02 December 2016 - 06:17 PM

Quote

Ok so then with each vertex, I find all the edges connected to that vertex

All the unvisited edges.

Quote

and then the smallest edge will always be at the front of the pq.

You throw the unvisited edges from said vertex v into the priority queue. The smallest weight edge incident to v is not necessarily at the head of the queue.

Note as well that vertices are visited in a breadth-first manner. Dijkstra's algorithm is essentially a greedy breadth-first traversal of the graph.

Quote

The only thing I'm wondering is how do I set up a priority queue?

This brings me back to my question from post #9:

Quote

An edge isn't an integer. What information does a weighted edge store?


In other words, how do you model an edge? Java is an Object-Oriented language, so an OO approach is a solid one here.

By the way- I think you have some holes in your understanding of Dijkstra's algorithm. I wrote a tutorial on Dijkstra's algorithm which you may find helpful. I would caution trying to graft my implementation onto yours, as I did not take an adjacency matrix approach with this. Instead, try to understand how the algorithm works.

I hope this helps!

This post has been edited by macosxnerd101: 02 December 2016 - 06:19 PM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1