Dijsktra for Adjacency matrix, Shortest and cheapest Path, single source, single target

Question

I'm trying to implement the Dijkstra algorithm in order to get the shortest and cheapest path from one vertex to another vertex, not for all vertices. The graph is built randomly by using random nodes which are connected with random weights.

But either I get negative costs or the path for both methods, cheapest and shortest, is the same. I'm trying to find both results by using the same method since shortest path is just ignoring the weights. This is controlled by a boolean variable.

Dijkstra - Class:

public class Dijkstra {

private Graph graph;
private int[] distance;
private boolean[] visited;
private int[] parents;
private int startNode;
private int endNode;

public Dijkstra(Graph graph, int startNode, int endNode) {
    this.graph = graph;
    distance = new int[graph.getAdjList().length];
    visited = new boolean[graph.getAdjList().length];
    parents = new int[graph.getAdjList().length];
    this.startNode = startNode;
    this.endNode = endNode;
}

public void findPath(boolean isUnweighted) {
    if (endNode == startNode) {
        System.out.println(
                "Starting node  " + startNode + "  and target node " + endNode + " are identical.");
        return;
    }
    System.out.println("Starting node: " + startNode);
    System.out.println("Target node:  " + endNode);
    int[][] adjList = graph.getAdjList();
    int[][] graphForPathFinding = new int[adjList.length][adjList.length];

    if (isUnweighted) {
        // set all weights to 1
        graphForPathFinding = convertGraphToUnweighted(graphForPathFinding);
    } else
        graphForPathFinding = adjList;
    // initialize
    for (int i = 0; i < adjList.length; i++) {
        parents[i] = Integer.MAX_VALUE;
        visited[i] = false;
        distance[i] = Integer.MAX_VALUE;
    }

    distance[startNode] = 0;
    for (int i = 0; i < graphForPathFinding.length; i++) {

        int nextNode = getMinDistance();
        if (nextNode == -1) { // no path found
            System.out.println(
                    "No path found between " + startNode + " and " + endNode);
            return;
        }
        visited[nextNode] = true;
        parents[i] = nextNode;

        if (nextNode == endNode) {
            printResults();
            return; // target node reached
        }
        int[] neighbors = graph.getNeighbors(nextNode);
        for (int j = 0; j < neighbors.length; j++) {

             if (!visited[j] && neighbors[j] > 0 && distance[nextNode] !=
             Integer.MAX_VALUE
             && distance[nextNode] + neighbors[j] < distance[j])
             distance[j] = distance[nextNode] + neighbors[j];
        }

    }

}

private int getMinDistance() {
    int min = Integer.MAX_VALUE;
    int min_index = -1;

    for (int i = 0; i < graph.getAdjList().length; i++) {
        if (visited[i] == false && distance[i] <= min) {
            min = distance[i];
            min_index = i;
        }

    }
    return min_index;
}

private int[][] convertGraphToUnweighted(int[][] graphForConverting) {
    for (int i = 0; i < graph.getAdjList().length; i++) {
        for (int j = 0; j < graph.getAdjList()[i].length; j++) {
             //if (graph.getAdjList()[i][j] > 0) {
            graphForConverting[i][j] = 1;
        // }
        }
    }
    return graphForConverting;
}

private void printResults() {
int weight = 0;
int steps = 0;
System.out.println("Pfad: ");
    for(int i = endNode; i>=0; i--){
        if(parents[i] < Integer.MAX_VALUE){
            System.out.print(parents[i] + "    ");
            steps++;
            weight += graph.getAdjList()[i][parents[i]];
        }

    }

    System.out.println();
    System.out.println("Number of nodes: " + steps);
     System.out.println("Weight:  " + weight);
}

}

Graph - Class getNeighbors

public int[] getNeighbors(int node){
        int neighborCount = 0;
        for(int i = 0; i < adjList[node].length; ++i)
            if(adjList[node][i] > 0)
                ++neighborCount;
        int[] neighbours = new int[neighborCount];
        neighborCount = 0;
        for(int i = 0; i < adjList[node].length; ++i)
            if(adjList[node][i] > 0)
                neighbours[neighborCount++] = i;

        return neighbours;
    }

Main - method:

 public static void main(String[] args) {
            int startNode = rnd.nextInt(graph.getAdjList().length);
            int endNode = rnd.nextInt(graph.getAdjList().length);
            Dijkstra d = new Dijkstra(graph, startNode, endNode);

            System.out.println("Shortest path:");
            d.findPath(true); // true = unweighted, false = weighted
            System.out.println();
            System.out.println("Cheapest path:");
            d.findPath(false);
}

MartinS MartinS · Accepted Answer · 2016-02-22T04:06:38

Ok it took me a while to figure out why and how your algorithm is broken because there are quite a few things wrong:

1. getMinDistance() is wrong

In this method you try to find the cheapest node to visit next which is the right idea but the implementation is wrong. First you are considering ALL nodes in the graph, not just the neighbors of the node you are currently visiting and secondly you use the distance array to look up the cost. But in there the values for all unvisited nodes are Integer.MAX_VALUE so the method will always choose the node with the highest index.

2. You are using the wrong Adjancency List

For the shortest path you are creating a modified copy of the original adjacency list, but then you are not using it.

3. Your modified Adjancency List is wrong

When creating the modified copy for shortest path, you set the value to 1 everywhere instead of 1 where there is an edge and Integer.MAX_VALUE for everything else (actually you should use -1 in that case and check for it in your code. Otherwise your algorithm will say that there is a path between nodes that are disconnected).

4. This is NOT Dijkstra

It took me a while to see that because sometimes you get the right result but this is not Dijkstra's Algorithm. To implement it properly you need a priority queue or some other mechanism to track the distances and get the minimum. You tried that with your 'getMinDistance' method but this approach was wrong because you considered all nodes in the graph and not only the ones 'in the queue'.

See below for a fixed version of your code. You should try to reimplement it yourself but since I have it now anyways...

public class Dijkstra {

  private static final class DijkstraComparator implements Comparator<Integer> {
    private final int[] distance;

    DijkstraComparator(int[] distance) {
        this.distance = distance;
    }

    @Override
    public int compare(Integer o1, Integer o2) {
        return Integer.compare(distance[o1], distance[o2]);
    }
  }

  private Graph graph;
  private int[] distance;
  private boolean[] visited;
  private int[] parents;
  private int startNode;
  private int endNode;

  public Dijkstra(Graph graph, int startNode, int endNode) {
    this.graph = graph;
    distance = new int[graph.getAdjList().length];
    visited = new boolean[graph.getAdjList().length];
    parents = new int[graph.getAdjList().length];
    this.startNode = startNode;
    this.endNode = endNode;
  }

  public void findPath(boolean isUnweighted) {
    if (endNode == startNode) {
        System.out.println("Starting node  " + startNode + "  and target node " + endNode + " are identical.");
        return;
    }

    int[][] graphForPathFinding;
    if (isUnweighted) {
        // set all weights to 1
        graphForPathFinding = convertGraphToUnweighted();
    } else {
        graphForPathFinding = graph.getAdjList();
    }

    // initialize
    for (int i = 0; i < parents.length; i++) {
        parents[i] = Integer.MAX_VALUE;
        visited[i] = false;
        distance[i] = Integer.MAX_VALUE;
    }

    PriorityQueue<Integer> queue = new PriorityQueue<>(1, new DijkstraComparator(distance));
    distance[startNode] = 0;
    queue.add(startNode);

    while (queue.isEmpty() == false) {
        int nextNode = queue.poll();
        visited[nextNode] = true;

        if (nextNode == endNode) {
            printResults();
            return; // target node reached
        }

        int[] neighbors = graph.getNeighbors(nextNode);
        for (int neighbor : neighbors) {
            if (visited[neighbor] == false) {
                // update distance
                int d = distance[nextNode] + graphForPathFinding[nextNode][neighbor];
                if (d < distance[neighbor]) {
                    distance[neighbor] = d;
                    parents[neighbor] = nextNode;

                    // remove neighbors from queue so the value gets updated
                    if (queue.contains(neighbor)) {
                        queue.remove(neighbor);
                    }
                    queue.add(neighbor);
                }
            }
        }
    }
    System.out.println("No path found between " + startNode + " and " + endNode);
  }

  private int[][] convertGraphToUnweighted() {
    int[][] adjMatrix = graph.getAdjList();
    int[][] graphForConverting = new int[adjMatrix.length][adjMatrix.length];
    for (int i = 0; i < adjMatrix.length; i++) {
        int[] adjList = adjMatrix[i];
        for (int j = 0; j < adjList.length; j++) {
            if (adjList[j] != 0) {
                graphForConverting[i][j] = 1;
            } else {
                graphForConverting[i][j] = Integer.MAX_VALUE;
            }
        }
    }
    return graphForConverting;
  }

  private void printResults() {
    int weight = 0;
    int steps = 0;
    System.out.println("Pfad: ");
    for (int node = endNode; node != startNode; steps++) {
        System.out.print(node + "    ");
        weight += graph.getAdjList()[parents[node]][node];
        node = parents[node];
    }
    System.out.println(startNode);
    System.out.println("Number of nodes: " + steps);
    System.out.println("Weight:  " + weight);
  }
}

Dijsktra for Adjacency matrix, Shortest and cheapest Path, single source, single target

1 Answers