IN JAVA. Assignment # 4 Shortest Path Algorithm Implementation of Dijkstra\'s Sh
ID: 3719344 • Letter: I
Question
IN JAVA.
Assignment # 4 Shortest Path Algorithm Implementation of Dijkstra's Shortest path algorithm Djikstra's algorithm (named after its discoverer, E.W. Dijkstra) solves the problem of finding the shortest patlh from a point in a graph (the source) to a destination. One can find the shortest paths from a given source to all points in a graph at the same time. Hence this problem is sometimes called the single-source shortest path problem. Dijkstra's algorithm finds the shortest path from x to y in order of increasing distance from x. That is, it chooses the first minimum edge, stores this value and adds the next minimum value from the next edge it selects. It starts out at one vertex and branches out by selecting certain edges that lead to new vertices. It is similar to the minimum spanning tree algorithm, in that it is "greedy", always choosing the closest edge in hope of an optimal solution. Pseudo Code for Dijkstra's Algorithm Void dijkstra(Vertex s) Vertex v.w: s.dist = 0: for() v = smallest unknown distance vertex: if(v--null) ?·known = true: for each w adjacent to v break if (!w.known) if (v.dist + cvwExplanation / Answer
public class Edge {
private int fromNode;
private int toNode;
private int len;
public Edge(int fromNode, int toNode, int len) {
this.fromNode = fromNode;
this.toNode = toNode;
this.len = len;
}
public int getfromNode() {
return fromNode;
}
public int gettoNode() {
return toNode;
}
public int getlen() {
return len;
}
// determines the neighbouring node of a supplied node,
// based on the two nodes connected by this edge
public int getNeighbourIndex(int nodeIndex) {
if (this.fromNode == nodeIndex) {
return this.toNode;
} else {
return this.fromNode;
}
}
}
//2.
import java.util.ArrayList;
public class Node {
private int distFromSrc = Integer.MAX_VALUE;
private boolean visited;
private ArrayList<Edge> edges = new ArrayList<Edge>(); // now we must create edges
public int getdistFromSrc() {
return distFromSrc;
}
public void setdistFromSrc(int distFromSrc) {
this.distFromSrc = distFromSrc;
}
public boolean isVisited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
public ArrayList<Edge> getEdges() {
return edges;
}
public void setEdges(ArrayList<Edge> edges) {
this.edges = edges;
}
}
//3.
import java.util.ArrayList;
public class Graph {
private Node[] nodes;
private int numOfNodes;
private Edge[] edges;
private int numOfEdges;
public Graph(Edge[] edges) {
this.edges = edges;
// creating all nodes that should ready to be updated with the edges
this.numOfNodes = calculateNoOfNodes(edges);
this.nodes = new Node[this.numOfNodes];
for (int n = 0; n < this.numOfNodes; n++) {
this.nodes[n] = new Node();
}
// adding all edges to the nodes, each edge added to two nodes (to node and from node).
this.numOfEdges = edges.length;
for (int edgeToAdd = 0; edgeToAdd < this.numOfEdges; edgeToAdd++) {
this.nodes[edges[edgeToAdd].getfromNode()].getEdges().add(edges[edgeToAdd]);
this.nodes[edges[edgeToAdd].gettoNode()].getEdges().add(edges[edgeToAdd]);
}
}
private int calculateNoOfNodes(Edge[] edges) {
int noOfNodes = 0;
for (Edge e : edges) {
if (e.gettoNode() > noOfNodes)
noOfNodes = e.gettoNode();
if (e.getfromNode() > noOfNodes)
noOfNodes = e.getfromNode();
}
noOfNodes++;
return noOfNodes;
}
// method to calculate shortest path distance !!
public void calShortestDistancePath() {
// node 0 as source
this.nodes[0].setdistFromSrc(0);
int nextNode = 0;
// visit every node
for (int i = 0; i < this.nodes.length; i++) {
// loop around the edges of current node
ArrayList<Edge> currentNodeEdges = this.nodes[nextNode].getEdges();
for (int joinedEdge = 0; joinedEdge < currentNodeEdges.size(); joinedEdge++) {
int neighbourIndex = currentNodeEdges.get(joinedEdge).getNeighbourIndex(nextNode);
// only if not visited
if (!this.nodes[neighbourIndex].isVisited()) {
int tentative = this.nodes[nextNode].getdistFromSrc() + currentNodeEdges.get(joinedEdge).getlen();
if (tentative < nodes[neighbourIndex].getdistFromSrc()) {
nodes[neighbourIndex].setdistFromSrc(tentative);
}
}
}
// all neighbours checked so node visited
nodes[nextNode].setVisited(true);
// next node must be with shortest distance
nextNode = getNodeShortestDistanced();
}
}
// now we're going to implement this method in next part !
private int getNodeShortestDistanced() {
int storedNodeIndex = 0;
int storedDist = Integer.MAX_VALUE;
for (int i = 0; i < this.nodes.length; i++) {
int currentDist = this.nodes[i].getdistFromSrc();
if (!this.nodes[i].isVisited() && currentDist < storedDist) {
storedDist = currentDist;
storedNodeIndex = i;
}
}
return storedNodeIndex;
}
// display result
public void printResultOfShortestPath() {
String output = "Number of nodes = " + this.numOfNodes;
output += " Number of edges = " + this.numOfEdges;
for (int i = 0; i < this.nodes.length; i++) {
output += (" The shortest distance from node 0 to node " + i + " is " + nodes[i].getdistFromSrc());
}
System.out.println(output);
}
public Node[] getNodes() {
return nodes;
}
public int getNoOfNodes() {
return numOfNodes;
}
public Edge[] getEdges() {
return edges;
}
public int getNoOfEdges() {
return numOfEdges;
}
}
//4.
public class Dijkstras {
?
?
public static void main(String[] args) {
Edge[] e = {
new Edge(0, 4, 2),
new Edge(1, 5, 1), new Edge(2, 4, 1), new Edge(3, 5, 4),
new Edge(4, 5, 2), new Edge(4, 6, 7), new Edge(4, 7, 2),
new Edge(0, 1, 3), new Edge(1, 3, 2), new Edge(1, 4, 3),
new Edge(5, 6, 4), new Edge(6, 7, 5),new Edge(0, 2, 1), new Edge(0, 3, 4)
};
Graph graph = new Graph(e);
graph.calShortestDistancePath();
graph.printResultOfShortestPath();
}
}
/* OUTPUT:-
Number of nodes = 8
Number of edges = 14
The shortest distance from node 0 to node 0 is 0
The shortest distance from node 0 to node 1 is 3
The shortest distance from node 0 to node 2 is 1
The shortest distance from node 0 to node 3 is 4
The shortest distance from node 0 to node 4 is 2
The shortest distance from node 0 to node 5 is 4
The shortest distance from node 0 to node 6 is 8
The shortest distance from node 0 to node 7 is 4
*/