Changes to the algorithm?

[cryo75]

For testing purposes, I changed the weight from double to a class Edge to that I can store more information for each edge:

public class Edge {
public double weight;
public int info1, info2;
public String info3;
}

First, after searching for paths, I noticed that the last vertex's weight for each path is 0. Why is this?

Second, how to get the edge used between 2 vertices because for each edge in the path, I need to get that info?

Third, what changes need to be done to make it an undirected graph, so that an edge from (v, w) is the same as (w, v)... without duplicating the number of edges required?

[yan-qi]

Question 3: you may not need to duplicate the edges but have to change those maps for fanins and fanouts by doubling their entries.

Question 2: you may need to maintain a map from vertices pair to edge; or you can change the way to define a path as a list of edges

Question 1: the weight in vertex is mostly used as intermediate results. You may want to check the weight of path to figure out the real weight.

Please let me know if you have any questions.

[cryo75]

Question 3: ok. I did that. I get the same paths, however, the search times are longer now.

Question 2: I don't that is necessary, because I added the Edge class instead of just double weight, so I added the following method:

    public Edge getEdge(int startVertexId, int endVertexId) {
    return vertexPairWeightIndex.get(new Pair<Integer, Integer>(startVertexId, endVertexId));
}

Question 1: Using the getEdge method I can return the edges between vertices, so I can build an edge path from a vertex path.

I have another Djikstra algorthim that uses fibonacci heaps. Would it be possible to use this algorithm instead of the one currently used?

[yan-qi]

Sure it is possible to replace the Dijkstra algorithm with yours.

If it works well, you are welcome to add your approach. :)

[cryo75]

Is a graph reusable?

What I mean is:
I create a graph only once. I then search many times with different sources and targets. Do I need to clear/reset intermediate weights of previous searches?

[yan-qi]

Yes, you need to reset the intermediate weights of previous searches because the source/sink pair changes

[cryo75]

So basically I added this method to the graph:

public void reset() {
    for (int i = 0; i < vertexList.size(); i++) {
        vertexList.get(i).setWeight(0);
    }
}

This should do it. Right?

Also, is the Dijkstra implementation bi-directional because there are 2 methods called updateCostForward and correctCostBackward.

[yan-qi]

The two methods in the Dijkstra implementation are defined not only for the shortest path calculation but also for the top-k shortest paths.

[vivid-]

When I am tring to find the 20 shorest paths between two nodes in a graph which has about 20000 edges, it takes like more than ten hours, is it normal?

[yan-qi]

To Vivid,

To be honest, I have never run the algorithm in such a big graph. Is it possible for you to send me the data? I want to have a try.