## Question

## Transcribed Text

## Solution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

import java.io.File;import java.io.FileNotFoundException;

import java.util.Comparator;

import java.util.HashMap;

import java.util.LinkedHashMap;

import java.util.Map;

import java.util.Scanner;

import java.util.Stack;

import java.util.stream.Collectors;

/**

*

* @author

*/

public class project {

private static String sequence;

public static void main(String[] args) {

// hashhmap all vertex in the graph

// each vertex is the key of another map

// which is contain the distacne between this vertex and other vertices

HashMap<Vertex, HashMap<Vertex, Integer>> graph;

graph = new HashMap<>();

// read file

readGraph(graph);

readDistanceToZ(graph);

Scanner scanner = new Scanner(System.in);

boolean valid = false;

do {

System.out.print("Enter start node: ");

String start = scanner.next();

System.out.println("User enters node " + start + " as the start node");

System.out.println("");

System.out.println("Algorithm 1: ");

System.out.println("");

valid = Algorithm1(start, graph);

System.out.println("");

System.out.println("Algorithm 2: ");

System.out.println("");

valid = valid && Algorithm2(start, graph);

// stop when the input is the name of a valid node

} while (valid == false);

}

private static boolean Algorithm2(String name,

HashMap<Vertex, HashMap<Vertex, Integer>> graph) {

// reset all vertices

for (Vertex vertex : graph.keySet()) {

vertex.setVisited(false);

}

// find the key

Vertex key = null;

for (Vertex vertex : graph.keySet()) {

if (vertex.getName().equals(name)) {

key = vertex;

break;

}

}

// invalid name

if (key == null) {

return false;

}

key.setVisited(true);

Stack<Vertex> stack = new Stack<>();

stack.push(key);

// call algorithm

sequence = name;

boolean result = Algorithm2(stack, graph);

if (result == true) {

System.out.println("\tSequence of all nodes: " + sequence);

System.out.println("\tShortest path: " + generatePath(stack));

System.out.println("\tShortest path length: "

+ generatePathLength(stack, graph));

} else {

System.out.println("There is no path");

}

return true;

}

private static boolean Algorithm2(Stack<Vertex> stack,

HashMap<Vertex, HashMap<Vertex, Integer>> graph) {

// current node

Vertex current = stack.peek();

// list adjacent nodes:

HashMap<Vertex, Integer> adj = graph.get(current);

/**

* Algorithm 2: Among all nodes v that are adjacent to the node n,

* choose the one for which w(n, v) + dd(v) is the smallest.

*/

Comparator<? super Map.Entry<Vertex, Integer>> comparator

= (Map.Entry<Vertex, Integer> o1, Map.Entry<Vertex, Integer> o2) -> {

HashMap<Vertex, Integer> value = graph.get(current);

int dd1 = value.get(o1.getKey()) + o1.getKey().getDistanceToZ();

int dd2 = value.get(o2.getKey()) + o2.getKey().getDistanceToZ();

return dd1 - dd2;

};

// sort the map by w(n, v) + dd(v)

Map<Vertex, Integer> sortedAdj = adj.entrySet()

.stream()

.sorted(comparator)

.collect(Collectors.toMap(

Map.Entry::getKey,

Map.Entry::getValue,

(oldValue, newValue) -> oldValue, LinkedHashMap::new));

/**

* work on each vertex

*/

for (Vertex vertex : sortedAdj.keySet()) {

sequence += " -> " + vertex.getName();

if (vertex.isVisited() == false) {

vertex.setVisited(true);

stack.push(vertex);

if (vertex.getName().equals("Z")) {

return true;

}

boolean result = Algorithm2(stack, graph);

if (result == true) {

return true;

}

// backtrack

stack.pop();

vertex.setVisited(false);

}

}

return false;

}

/**

* algorithm 1

*

* @param name name of the starting point

* @param graph the graph

* @return return false when key is invalid

*/

private static boolean Algorithm1(String name,

HashMap<Vertex, HashMap<Vertex, Integer>> graph) {

// reset all vertices

for (Vertex vertex : graph.keySet()) {

vertex.setVisited(false);

}

// find the key

Vertex key = null;

for (Vertex vertex : graph.keySet()) {

if (vertex.getName().equals(name)) {

key = vertex;

break;...

By purchasing this solution you'll be able to access the following files:

Solution.zip.