6 4 2 4 5 4 Use JAVA Using the principles from a circular doubly linked list, so

ID: 3739685 • Letter: 6

Question

6 4 2 4 5 4 Use JAVA Using the principles from a circular doubly linked list, solve Dijkstra's algorithm for the longest and shortest paths from A to N in the diagram above. In this example the Node will have multiple data objects (name, path speeds) and a previous and next node object. Note that some nodes will have more than two paths. That next or previous path will depend on the path speed. Write an algorithm that will build the algorithm as a class then solve the puzzle. Extra credit for any one who also randomizes the paths speeds (0sps>6).

Explanation / Answer

public class Graph {

private Set<Node> nodes = new HashSet<>();

public void addNode(Node nodeA) {

nodes.add(nodeA);

}

// getters and setters

}

public class Node {

private String name;

private List<Node> shortestPath = new LinkedList<>();

private Integer distance = Integer.MAX_VALUE;

Map<Node, Integer> adjacentNodes = new HashMap<>();

public void addDestination(Node destination, int distance) {

adjacentNodes.put(destination, distance);

}

public Node(String name) {

this.name = name;

}

// getters and setters

}

public static Graph calculateShortestPathFromSource(Graph graph, Node source) {

source.setDistance(0);

Set<Node> settledNodes = new HashSet<>();

Set<Node> unsettledNodes = new HashSet<>();

unsettledNodes.add(source);

while (unsettledNodes.size() != 0) {

Node currentNode = getLowestDistanceNode(unsettledNodes);

unsettledNodes.remove(currentNode);

for (Entry < Node, Integer> adjacencyPair:

currentNode.getAdjacentNodes().entrySet()) {

Node adjacentNode = adjacencyPair.getKey();

Integer edgeWeight = adjacencyPair.getValue();

if (!settledNodes.contains(adjacentNode)) {

calculateMinimumDistance(adjacentNode, edgeWeight, currentNode);

unsettledNodes.add(adjacentNode);

}

settledNodes.add(currentNode);

}

return graph;

}

private static Node getLowestDistanceNode(Set < Node > unsettledNodes) {

Node lowestDistanceNode = null;

int lowestDistance = Integer.MAX_VALUE;

for (Node node: unsettledNodes) {

int nodeDistance = node.getDistance();

if (nodeDistance < lowestDistance) {

lowestDistance = nodeDistance;

lowestDistanceNode = node;

}

return lowestDistanceNode;

}

private static void CalculateMinimumDistance(Node evaluationNode,

Integer edgeWeigh, Node sourceNode) {

Integer sourceDistance = sourceNode.getDistance();

if (sourceDistance + edgeWeigh < evaluationNode.getDistance()) {

evaluationNode.setDistance(sourceDistance + edgeWeigh);

LinkedList<Node> shortestPath = new LinkedList<>(sourceNode.getShortestPath());

shortestPath.add(sourceNode);

evaluationNode.setShortestPath(shortestPath);

}}

Node nodeA = new Node("A");

Node nodeB = new Node("B");

Node nodeC = new Node("C");

Node nodeD = new Node("D");

Node nodeE = new Node("E");

Node nodeF = new Node("F");

nodeA.addDestination(nodeB, 5);

nodeA.addDestination(nodeC, 4);

nodeB.addDestination(nodeD, 4);

nodeB.addDestination(nodeF, 6);

nodeC.addDestination(nodeE, 6);

nodeD.addDestination(nodeE, 8);

nodeD.addDestination(nodeF, 3);

nodeF.addDestination(nodeE, 2);

Graph graph = new Graph();