Question

Please follow all the instructions and do all the parts (a-d)!

Create a Java program which implements Dijkstra’s shortest path algorithm according to the psueudocode below. Base the design on the weighted graph implementation used in Problem3.java (provided at the bottom). Your program should include the following features:

a. A new method receives a starting vertex index and a target vertex index (e.g. 0 and 4). It computes the shortest distances to all vertexes using Dijkstra’s algorithm. The pseudocode is given below:

b. In the method for (a), print the values of the arrays “allowed” and “distance” at the end of each iteration of the outer loop (after “distance” has been updated).

c. In the method for (a), print the vertexes of the shortest path to the target. If there is no path, the algorithm should still work by printing a warning message. Note that printing the path requires storing the “predecessor” values. The path vertexes should be printed in order, beginning with the starting vertex. To reverse the default order, you may use the Stack class, if desired.

d. A main() method demonstrates the method for (a).

Below is an example of a graph and the expected output for the path from v0 to v4. Though not required, the output below adds some extra messages to indicate the initial values and when the loop is about to be executed.

Below is an example using the same graph for a path from v4 to v0, which is not valid. We know it is not valid because the distance to v0 is Infinity.

Problem3.java:

public class Problem3 implements Cloneable {
    private double[ ][ ] edges;
    private Object[ ] labels;

    public Problem3(int n) {
        edges = new double[n][n];
        labels = new String[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                edges[i][j] = -1.0;
            }
        }
    }

    public void addEdge(int source, int target, double weight) {
        edges[source][target] = weight;
    }

    public double getWeight(int source, int target) {
        return edges[source][target];
    }

    public void printTotalPath(int[] vertex) {
        double weight = 0.0;
        boolean valid = true;
        System.out.print("The path from " + getLabel(vertex[0]));
        for (int i = 1; i < vertex.length; i++) {
            weight += edges[vertex[i-1]][vertex[i]];
            if (!isEdge(vertex[i-1], vertex[i]))
                valid = false;
            System.out.print(" to " + getLabel(vertex[i]));
        }
        if (valid)
            System.out.println(" is " + weight + ".");
        else
            System.out.println(" is not valid.");
    }

    public static void depthFirstPrint(Graph g, int start) {
        boolean[ ] marked = new boolean [g.size( )];

        depthFirstRecurse(g, start, marked);

    }

    public static void depthFirstRecurse(Graph g, int v, boolean[ ] marked) {
        int[ ] connections = g.neighbors(v);
        int i;
        int nextNeighbor;

        marked[v] = true;
        System.out.println(g.getLabel(v));

        for (i = 0; i < connections.length; i++) {
            nextNeighbor = connections[i];
            if (!marked[nextNeighbor])
                depthFirstRecurse(g, nextNeighbor, marked);
        }
    }

    public Object getLabel(int vertex) {
        return labels[vertex];
    }

    public boolean isEdge(int source, int target) {
        return edges[source][target] >= 0;
    }

    public void removeEdge(int source, int target) {
        edges[source][target] = -1;
    }

    public void setLabel(int vertex, Object newLabel) {
        labels[vertex] = newLabel;
    }

    public int size( ) {
        return labels.length;
    }

    public static void main(String[] args) {
        Problem3 graph = new Problem3(4);
        graph.setLabel(0, "Byteville");
        graph.setLabel(1, "Bitburg");
        graph.setLabel(2, "Nulltown");
        graph.setLabel(3, "Binaria");
        graph.addEdge(0,1, 1.5);
        graph.addEdge(1,2, 2.2);
        graph.addEdge(2,3, 1.4);
        graph.addEdge(3,0, 3.9);
        int[] path1 = {1, 2, 3};
        graph.printTotalPath(path1);
        int[] path2 = {0, 2, 3};
        graph.printTotalPath(path2);
    }

}

3 7 0 6 2 5 1 2 8 Initial values... allowed: false false false false false false distance: Infinity Infinity Infinity Infinity 0.0 Infinity Executing loop... allowed: false false false false true false distance : Infinity Infinity 7.0 3.0 0.0 Infinity allowed: false false false true true false distance : Infinity Infinity 7.0 3.0 0.0 Infinity allowed: false false true true true false distance: Infinity Infinity 7.0 3.00.0 Infinity allowed: false false true true true false distance: Infinity Infinity 7.0 3.0 0.0 Infinity allowed: false false true true true false distance: Infinity Infinity 7.03.0 0.0 Infinity There is no path from 4 to0

Answer 1

Dijkstra's shotest path code in java

import java.util.PriorityQueue;

import java.util.List;

import java.util.ArrayList;

import java.util.Collections;

public class DijkstraAlgo{

/* Dijkstra Algorithm

*

*

*/

public static void computePaths(Node source){

source.shortestDistance=0;

//implement a priority queue

PriorityQueue<Node> queue = new PriorityQueue<Node>();

queue.add(source);

while(!queue.isEmpty()){

Node u = queue.poll();

/*visit the adjacencies, starting from

the nearest node(smallest shortestDistance)*/

for(Edge e: u.adjacencies){

Node v = e.target;

double weight = e.weight;

//relax(u,v,weight)

double distanceFromU = u.shortestDistance+weight;

if(distanceFromU<v.shortestDistance){

/*remove v from queue for updating

the shortestDistance value*/

queue.remove(v);

v.shortestDistance = distanceFromU;

v.parent = u;

queue.add(v);

}

}

}

}

public static List<Node> getShortestPathTo(Node target){

//trace path from target to source

List<Node> path = new ArrayList<Node>();

for(Node node = target; node!=null; node = node.parent){

path.add(node);

}

//reverse the order such that it will be from source to target

Collections.reverse(path);

return path;

}

public static void main(String[] args){

//initialize the graph base on the Romania map

Node n1 = new Node("Arad");

Node n2 = new Node("Zerind");

Node n3 = new Node("Oradea");

Node n4 = new Node("Sibiu");

Node n5 = new Node("Fagaras");

Node n6 = new Node("Rimnicu Vilcea");

Node n7 = new Node("Pitesti");

Node n8 = new Node("Timisoara");

Node n9 = new Node("Lugoj");

Node n10 = new Node("Mehadia");

Node n11 = new Node("Drobeta");

Node n12 = new Node("Craiova");

Node n13 = new Node("Bucharest");

Node n14 = new Node("Giurgiu");

//initialize the edges

n1.adjacencies = new Edge[]{

new Edge(n2,75),

new Edge(n4,140),

new Edge(n8,118)

};

n2.adjacencies = new Edge[]{

new Edge(n1,75),

new Edge(n3,71)

};

n3.adjacencies = new Edge[]{

new Edge(n2,71),

new Edge(n4,151)

};

n4.adjacencies = new Edge[]{

new Edge(n1,140),

new Edge(n5,99),

new Edge(n3,151),

new Edge(n6,80),

};

n5.adjacencies = new Edge[]{

new Edge(n4,99),

new Edge(n13,211)

};

n6.adjacencies = new Edge[]{

new Edge(n4,80),

new Edge(n7,97),

new Edge(n12,146)

};

n7.adjacencies = new Edge[]{

new Edge(n6,97),

new Edge(n13,101),

new Edge(n12,138)

};

n8.adjacencies = new Edge[]{

new Edge(n1,118),

new Edge(n9,111)

};

n9.adjacencies = new Edge[]{

new Edge(n8,111),

new Edge(n10,70)

};

n10.adjacencies = new Edge[]{

new Edge(n9,70),

new Edge(n11,75)

};

n11.adjacencies = new Edge[]{

new Edge(n10,75),

new Edge(n12,120)

};

n12.adjacencies = new Edge[]{

new Edge(n11,120),

new Edge(n6,146),

new Edge(n7,138)

};

n13.adjacencies = new Edge[]{

new Edge(n7,101),

new Edge(n14,90),

new Edge(n5,211)

};

n14.adjacencies = new Edge[]{

new Edge(n13,90)

};

Node[] nodes = {n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11,n12,n13,n14};

//compute paths

computePaths(n1);

//print shortest paths

/*

for(Node n: nodes){

System.out.println("Distance to " +

n + ": " + n.shortestDistance);

List<Node> path = getShortestPathTo(n);

System.out.println("Path: " + path);

}*/

List<Node> path = getShortestPathTo(n13);

System.out.println("Path: " + path);

}

}

//define Node

class Node implements Comparable<Node>{

public final String value;

public Edge[] adjacencies;

public double shortestDistance = Double.POSITIVE_INFINITY;

public Node parent;

public Node(String val){

value = val;

}

public String toString(){

return value;

}

public int compareTo(Node other){

return Double.compare(shortestDistance, other.shortestDistance);

}

}

//define Edge

class Edge{

public final Node target;

public final double weight;

public Edge(Node targetNode, double weightVal){

target = targetNode;

weight = weightVal;

}

}
Sign up for free