Different shortest path for each test

Question

I'm writing a program counting average delay in given network. I use a JUNG library. On input my program reads information how many packets vertex x want to send to vertex y for second. My graph is unweighted and I assume that packets are sending by shortest path.

I use JUNG methods to get shortest path:

public class NetworkGraph {

    protected final Graph graph;

    protected Vertex[] vertices;
    protected Random random;
    protected double sumOfFlowStrengthMatrix;

    protected final int[][] flowStrengthMatrix;



    NetworkGraph(Input input, Graph graph) {
        random = new Random();
        this.graph = graph;

        loadVertices(input);
        loadEdges(input);
        loadSumOfFlowStrengthMatrix(input);
        flowStrengthMatrix = input.getFlowStrengthMatrix();
    }

    private void loadVertices(Input input) {
        vertices = new Vertex[input.getNumberOfVertices()];

        for (int i = 0; i < input.getNumberOfVertices(); i++) {
            vertices[i] = new Vertex(i + 1);
            graph.addVertex(vertices[i]);
        }
    }

    private void loadEdges(Input input) {
        for (int i = 0; i < input.getNumberOfVertices(); i++) {
            for (int j = 0; j < input.getNumberOfVertices(); j++) {
                if (input.getProbabilityOfDivulsionArray()[i][j] != 0) {
                    if (graph.findEdge(vertices[i], vertices[j]) == null) {
                        graph.addEdge(new Edge(input.getCapacityArray()[i][j], input.getProbabilityOfDivulsionArray()[i][j]), vertices[i], vertices[j]);
                    }
                }
            }
        }
    }

    private void loadSumOfFlowStrengthMatrix(Input input) {
        double sum = 0;

        for (int i = 0; i < input.getNumberOfVertices(); i++) {
            for (int j = 0; j < input.getNumberOfVertices(); j++) {
                sum += input.getFlowStrengthMatrix()[i][j];
            }
        }

        this.sumOfFlowStrengthMatrix = sum;
    }


    public double countAveragePacketDelayInNetwork() throws EdgeException {
        double out = 0;
        ArrayList<Edge> edges = new ArrayList<>(graph.getEdges());

        recountFlows();

        for (Edge e : edges) {
            out += e.getAveragePacketDelay();
        }

        return round((out / sumOfFlowStrengthMatrix), 4);
    }

    protected void recountFlows() {
        for (int i = 0; i < vertices.length; i++) {
            for (int j = 0; j < vertices.length; j++) {
                DijkstraShortestPath<Vertex, Edge> algorithm = new DijkstraShortestPath<>(graph);
                List<Edge> edges = algorithm.getPath(vertices[i], vertices[j]);

                for (Edge edge : edges) {
                    edge.addToFlowStrength(flowStrengthMatrix[i][j]);
                }
            }
        }
    }
}

I ran my program several times with the same sample graph. Unfortunately I got a different results - for each time I have different average delay - it's really annoying.

Probably it's caused by Dijkstra algorithm - I noticed that Dijkstra algorithm returns different results for the same input. I know that it can be many shortest path from x to y, but why Dijkstra algorithm returns different paths when the input and way of creating graph is exactly the same every time?

Is there any way to make this algorithm returns always the same shortest path for given x and y?

Did you write the DijkstraShortestPath class? If so, please post the code. — Tony_craft
What exactly does the function loadEdges()? It seems it is using a probability in the first if statement. If that is true that could be the reason of the different outputs for the same input. — Tony_craft

Joshua O'Madadhain Joshua O'Madadhain · Accepted Answer · 2014-03-30T07:10:18

As Tony_craft said, we lack enough information about how the graph is built that a definitive answer is not possible.

However, there are two basic reasons why you might be getting different paths each time: (1) The graph is not the same each time. (2) The edges are being iterated over in a different order and you're getting a different edge of the same weight. Order of iteration over a Set (of outgoing edges) is not guaranteed to be consistent.

Different shortest path for each test

1 Answers