使用Java代写数据结构的Graph作业，查找最短路径，算法采用 Dijkstra’s algorithm
来实现。
NOTE
THE ASSIGNMENTS WILL BE GRADED USING AUTOMATED SCRIPTS SO PLEASE FOLLOW THE
SUBMISSION GUIDELINES PROVIDED. PLEASE GO THROUGH THIS ENTIRE DOCUMENT BEFORE
CODING AND SUBMITTING THE ASSIGNMENT.
Problem
Complete the code to find the SHORTEST PATH from a given origin vertex in
Graph G(V, E) to every other vertex V in graph G.
Use the classes and interface provided in Project2.zip
The Project2.zip contains Graph.java, GraphInterface.java, Test.java and
input.txt
ADD YOUR CODE to below method in Graph.java
public void dijkstra(int graph[][], int src, ArrayList
—|—
DO NOT MODIFY ANY OTHER METHODS AND FILES.
Sample input provided in input.txt file. All inputs will have a connecting
path between every pair of vertices and the connecting path may consist of one
or more edges.
EXPLANATION in COMMENTS FOR INPUT in input.txt file BELOW
3 5 3 //NUMBER_OF_VERTICES NUMBER_OF_EDGES NUMBER_OF_ORIGINS
A //NAME_OF_VERTEX_WITH_INDEX_0
B //NAME_OF_VERTEX_WITH_INDEX_1
C //NAME_OF_VERTEX_WITH_INDEX_2
0 1 1 //EDGE FROM VERTEX_A (INDEX_0) TO VERTEX_B (INDEX_1) and WEIGHT_1
1 2 3 //EDGE FROM VERTEX_B (INDEX_1) TO VERTEX_C (INDEX_2) and WEIGHT_3
2 0 7 //EDGE FROM VERTEX_C (INDEX_2) TO VERTEX_A (INDEX_0) and WEIGHT_7
2 1 4 //EDGE FROM VERTEX_C (INDEX_2) TO VERTEX_B (INDEX_1) and WEIGHT_4
1 0 2 //EDGE FROM VERTEX_B (INDEX_1) TO VERTEX_A (INDEX_0) and WEIGHT_2
A //ORIGIN IS A
B //ORIGIN IS B
C //ORIGIN IS C
NOTE: The 2-dimensional array ‘edges’ is used to denote the graph with cost of
edge. In the example above Vertex A is referred by index 0 and similarly
Vertex B by index 1 and Vertex C by index 2.
The graph G(V, E) for the above input in input.txt file is as below:
The output for the above input in input.txt file should be as below:
All shortest paths from A are:
A path from A to A: A (cost: 0.0)
A path from A to B: A B (cost: 1.0)
A path from A to C: A B C (cost: 4.0)
All shortest paths from B are:
A path from B to A: B A (cost: 2.0)
A path from B to B: B (cost: 0.0)
A path from B to C: B C (cost: 3.0)
All shortest paths from C are:
A path from C to A: C B A (cost: 6.0)
A path from C to B: C B (cost: 4.0)
A path from C to C: C (cost: 0.0)
Since the input had 3 origins A, B, C the output shows shortest paths to every
other node from all the three origins A,B,C. DO NOT WRITE YOUR OWN METHOD TO
DISPLAY THE OUTPUT.
Hints
- The edges[][] in Test.java will contain the graph with edges as below
- The method dijkstra in Graph.java for above input in input.txt file should be as below
* a. When Origin is A the shortest distance tree is as below
* b. When Origin is B the shortest distance tree is as below
* c. When Origin is C the shortest distance tree is as below
NOTE: The code should be tested using Test.java class provided in
project2.java. DO NOT WRITE ANY METHOD TO PRINT THE OUTPUT. Test.java will
call the appropriate method to print the output.
ECLIPSE IDE: If you are using any IDE the input file should be read from path
“src/input.txt”. If you are using java command from a terminal or command
prompt read file using only file name “input.txt”.
SUBMISSION DETAILS
Assignment will be graded using automated scripts so please make sure you
follow the below-mentioned submission guidelines
- DO NOT USE ‘/ __ /‘ for comments, use ‘//‘ instead.
- Create a new folder for your group. Example: For Group 1, create a directory/folder called Group1. DO NOT USE ANY SPACES OR SPECIAL CHARACTERS FOR THE DIRECTORY NAME.
- Copy all the four files Graph.java (Complete with your code), GraphInterface.java, Test.java and input.txt in your group directory.
- DO NOT SUBMIT OR COPY NETBEANS PROJECT OR ECLISPSE PROJECT TO THE DIRECTORY. PLEASE ONLY SUBMIT THE JAVA FILES INSIDE AN DIRECTORY.
- DO NOT ALTER THE INPUT METHOD FOR FILE IN TEST.JAVA FILE. If you do then make sure you set the input file path in Test.java is “input.txt” as the assignment will be graded through the terminal. i.e. below code should be used to read the input file in Test.java
File file = new File("input.txt") - Java version 8 should be used for compiling and executing the code.
- Your code should now compile from command prompt or terminal using: javac *.java
- Run your code using java Test and check the output in terminal or command prompt
- If everything is working fine, zip the directory for your group created in step 1. Example for group 1 a zip archive Group1.zip will be created.
- Make sure your zip folder contains a single folder with all four files Graph.java (Complete with your code), GraphInterface.java, Test.java and input.txt files inside the folder. Example: For Group 1, the hierarchy should be like the following
- Finally, submit Group1.zip archive in canvas.
COMMON QUESTIONS ASKED BY STUDENTS
Q1: What is a generic type ? and how to use it ?
Ans: Generic methods and classes help to perform operations on varibles
regrdless of data type. Using generics, you can Integer/String/Double etc. for
same class or method that use generics.
Sample code:
public class GenericMethodTest {
// generic method printArray
public static < E > void printArray( E[] inputArray ) {
// Display array elements
for(E element : inputArray) {
System.out.printf(“%s “, element);
}
System.out.println();
}
public static void main(String args[]) {
// Create arrays of Integer, Double and Character
Integer[] intArray = { 1, 2, 3, 4, 5 };
Double[] doubleArray = { 1.1, 2.2, 3.3, 4.4 };
Character[] charArray = { ‘H’, ‘E’, ‘L’, ‘L’, ‘O’ };
System.out.println(“Array integerArray contains:”);
printArray(intArray); // pass an Integer array
System.out.println(“\nArray doubleArray contains:”);
printArray(doubleArray); // pass a Double array
System.out.println(“\nArray characterArray contains:”);
printArray(charArray); // pass a Character array
}
}
—|—
Output
Array integerArray contains:
1 2 3 4 5
Array doubleArray contains:
1.1 2.2 3.3 4.4
Array characterArray contains:
H E L L O
Refer following URLs for detailed info:
https://www.tutorialspoint.com/java/java_generics.htm
https://www.geeksforgeeks.org/generics-in-java/
Q2: How to convert generic “T” into “int” ?
Ans: If you want to have an int representation, you should use the .intValue()
function.
int i = T.intValue();
—|—
Q3: Why should we use generic instead fixed data type such as “int” or
“String” ?
Ans: Using generics, you can provide input in any form regardless of a strict
data type. It is always a good approach to keep the user free from any
restriction or limitation.
Sample Code:
// A Simple Java program to show working of user defined
// Generic classes
// We use < > to specify Parameter type
class Test
// An object of type T is declared
T obj;
Test(T obj) { this.obj = obj; } // constructor
public T getObject() { return this.obj; }
}
// Driver class to test above
class Main {
public static void main (String[] args)
{
// instance of Integer type
Test
System.out.println(iObj.getObject());
// instance of String type
Test
System.out.println(sObj.getObject());
}
}
—|—
Output
GeeksForGeeks
Q4: What is hashMap and how to use it ?
Ans: HashMap is a part of Java’s collection since Java 1.2. It provides the
basic implementation of Map interface of Java. It stores the data in (Key,
Value) pairs.
https://www.geeksforgeeks.org/java-util-hashmap-in-java/
Sample Code:
// Java program to illustrate
// Java.util.HashMap
import java.util.HashMap;
import java.util.Map;
public class GFG {
public static void main(String[] args)
{
HashMap<String, Integer> map = new HashMap<>();
print(map);
map.put(“vishal”, 10);
map.put(“sachin”, 30);
map.put(“vaibhav”, 20);
System.out.println(“Size of map is:- “ + map.size());
print(map);
if (map.containsKey(“vishal”))
{
Integer a = map.get(“vishal”);
System.out.println(“value for key "vishal" is:- “ + a);
}
map.clear();
print(map);
}
public static void print(Map<String, Integer> map)
{
if (map.isEmpty())
{
System.out.println(“map is empty”);
}
else
{
System.out.println(map);
}
}
}
—|—
Output
map is empty
Size of map is:- 3
{vaibhav=20, vishal=10, sachin=30}
value for key "vishal" is: -10
map is empty
Q4: How to avoid ‘nullPointerException’?
Ans: Null pointer exception arises when you try to access an un-initialized
variable. Always check if you have initialized the variable or not before
accessing it or doing any operations on it.
Sample:
String s;
s.lenght(); //This will cause null pointer exception since ‘s’ is not initialized
s = “abc”; //initialize variable ‘s’
s.length(); //This will avoid nullPointerException
—|—
