The most commonly encountered problem associated with weighted graphs is of find
ID: 3713381 • Letter: T
Question
The most commonly encountered problem associated with weighted graphs is of finding the shortest path between two given vertices. Let us consider the Air Route plan shown below. We just want to find the cheapest route from one city to another.
The Airways charges passengers a fixed fare to travel between any two cities. These fares are shown in the figure. That is, the fare from Muscat to Suhar is OMR 50, from Suhar to Salalah is OMR 90, and so on. The edges are directed. They represent single-track airway routes, on which travel is permitted in only one direction. For example, you can go directly from Muscat to Suhar, but not from Suhar to Muscat. The problem is to find the shortest path which doesn’t necessarily mean in terms of distance; it can also mean cheapest, fastest, or best route by some measure. Write a report to analyze the above problem and mention the type of methodology you will adopt as a solution to the problem. Which algorithm is best suited for this problem? And develop a program using the Java programming language to find the shortest path from a specified vertex.
Blackboard Learn ×> DCourse project 2a-ITDR3X4 Google Translate × 1 ? d ? bb.cas.eduom/bbcswebdav/pid-428694-dt-content-rid-1069971-1/coursesATDR3103SOH-18SP-40/Course%20project%202a-ITDR3103-18SP.pdf The most commonly encountered problem associated with weighted graphs is of finding the shortest path between two given vertices. Let us consider the Air Route plan shown below. We just want to find the cheapest route from one city to another SUHAR ABU DHABI OMR 60 OMR 50 OMR 50 OMR 40 OMR 90 MUSCAT A OMR 80 OMR 20 OMR 70 DUBAI SALALAH S:51 PM ?40 ENG 22-Apr-18Explanation / Answer
import java.util.Scanner;
// Class ShortestPathRDijkstrasAlgorithm definition
class ShortestPathRDijkstrasAlgorithm
{
private static final int NO_PARENT = -1;
// Method to find shortest path using dijkstra's algorithm
private static void findShortestPath(int[][] adjacencyMatrix, int startVertex)
{
// Stores the adjacency matrix zero index position length
int numVertices = adjacencyMatrix[0].length;
// shortestDistances[i] will hold the shortest distance from source to position
int[] shortestDistances = new int[numVertices];
// added[position] will true if vertex position is included / in shortest path tree
// or shortest distance from source to position is finalized
boolean[] addedVertices = new boolean[numVertices];
// Initialize all distances as INFINITE and added[] as false
for (int vertexIndex = 0; vertexIndex < numVertices; vertexIndex++)
{
shortestDistances[vertexIndex] = Integer.MAX_VALUE;
addedVertices[vertexIndex] = false;
}// End of for loop
// Distance of source vertex from itself is always 0
shortestDistances[startVertex] = 0;
// Parent array to store shortest path tree
int[] shortestPathTree = new int[numVertices];
// The starting vertex does not have a parent
shortestPathTree[startVertex] = NO_PARENT;
// Find shortest path for all vertices
for (int position = 1; position < numVertices; position++)
{
// Pick the minimum distance vertex from the set of vertices not yet processed.
// nearestVertex is always equal to startNode in first iteration.
int nearestVertex = -1;
// Stores the maximum integer value as the initial shortest distance
int shortestDistance = Integer.MAX_VALUE;
// Loops till vertexIndex is less than numVertices
for (int vertexIndex = 0; vertexIndex < numVertices; vertexIndex++)
{
// Checks if the added vertices array's vertex index position is not true
// and shortest distance array's vertex index position value is less than the shortest distance
if (!addedVertices[vertexIndex] && shortestDistances[vertexIndex] < shortestDistance)
{
// Assigns the vertex index position value as the nearest vertex value
nearestVertex = vertexIndex;
// Updates the shortest distance as the vertex index position of shortest distance array value
shortestDistance = shortestDistances[vertexIndex];
}// End of if condition
}// End of for loop
// Mark the picked vertex as processed by assigning true
addedVertices[nearestVertex] = true;
// Update distance value of the adjacent vertices of the picked vertex.
for (int vertexIndex = 0; vertexIndex < numVertices; vertexIndex++)
{
int edgeDistance = adjacencyMatrix[nearestVertex][vertexIndex];
// Checks if edge distance value is greater than zero
// and shortest distance added value to edge distance value is less than the
// vertex index position of shortest distance value
if (edgeDistance > 0 && ((shortestDistance + edgeDistance) < shortestDistances[vertexIndex]))
{
// Assigns the nearest vertex value as the shortest path
shortestPathTree[vertexIndex] = nearestVertex;
// Adds the shortest distance with edge distance and
// assigns it to shortest distance array's vertex index position
shortestDistances[vertexIndex] = shortestDistance + edgeDistance;
}// End of if condition
}// End of for loop
}// End of outer for loop
// Calls the method to display the solution
displaySolution(startVertex, shortestDistances, shortestPathTree);
}// End of method
// Method to display the distances array and shortest paths
private static void displaySolution(int startVertex, int[] distances, int[] shortestPathTree)
{
int numVertices = distances.length;
// Displays the heading
System.out.print("Vertex Distance Path");
// Loops till number of vertex
for (int vertexIndex = 0; vertexIndex < numVertices; vertexIndex++)
{
// Checks if the vertex index is not start vertex
if (vertexIndex != startVertex)
{
// Displays the start vertex
System.out.print(" " + startVertex + " -> ");
// Displays next vertex
System.out.print(vertexIndex + " ");
// Displays the distance
System.out.print(distances[vertexIndex] + " ");
// Calls the method to display the path
displayShortestPath(vertexIndex, shortestPathTree);
}// End of if condition
}// End of for loop
}// End of method
// Method to display shortest path from source to currentVertex using parents array
private static void displayShortestPath(int currentVertex, int[] parents)
{
// Source node has been processed
if (currentVertex == NO_PARENT)
return;
// Recursively calls the method to display the shortest path
displayShortestPath(parents[currentVertex], parents);
// Displays the current vertex
System.out.print(currentVertex + " ");
}// End of method
// main function definition
public static void main(String[] s)
{
// Scanner class object created
Scanner sc = new Scanner(System.in);
// To store the starting vertex entered by the user
int startVertex;
// Creates an matrix for adjacency matrix
int[][] adjacencyMatrix = { { 0, 4, 0, 0, 12, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 3, 0 },
{ 12, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 9, 4, 0, 10, 0, 2, 6, 0 },
{ 0, 0, 0, 14, 0, 2, 0, 1, 6 },
{ 7, 9, 0, 0, 0, 0, 2, 0, 7 },
{ 0, 0, 2, 0, 12, 0, 8, 4, 0 } };
// Accepts the starting vertex from the user
System.out.print(" Enter the starting vertex: ");
startVertex = sc.nextInt();
// Calls the method to find out shortest path
findShortestPath(adjacencyMatrix, startVertex);
// Close scanner
sc.close();
}// End of main method
}// End of class
Sample Output:
Enter the starting vertex: 2
Vertex Distance Path
2 -> 0 12 2 1 0
2 -> 1 8 2 1
2 -> 3 7 2 3
2 -> 4 14 2 8 4
2 -> 5 4 2 5
2 -> 6 6 2 5 6
2 -> 7 6 2 8 7
2 -> 8 2 2 8
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.