In java language Design and implement a program to read information about roads
ID: 3713479 • Letter: I
Question
In java language
Design and implement a program to read information about roads connecting a set of cities and find the shortest path between two cities entered by the user.
Input File:
Input consists of information about the roads connecting the set of cities. The first line of input contains 2 integer M and N where indicated the number of cities and M the number of roads. The next M lines contain the description of the roads. Each road is described by 3 numbers S, D, L, where S and D are cities numbers and L is the distance between them.
Output:
A line containing the shortest distance to go from city S to D.
Sample input:
5 10
0 1 16
0 3 2
0 4 3.0
1 2 5
2 1 3
3 1 12
3 4 7
4 1 10
4 2 4
4 3 5
Sample output
The shortest distance between 0 and 1 is 10
Explanation / Answer
import java.util.*;
import java.lang.*;
import java.io.*;
class DjShortPath
{
// A utility function to find the vertex with minimum distance value,
// from the set of vertices not yet included in shortest path tree
static int V=9;
int minDistance(int dist[], Boolean sptSet[])
{
// Initialize min value
int min = Integer.MAX_VALUE, min_index=-1;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
{
min = dist[v];
min_index = v;
}
return min_index;
}
// function to print the constructed distance array
void printSP(int dist[], int n)
{
System.out.println("Vertex Distance from Source");
for (int i = 0; i < V; i++)
System.out.println(i+" "+dist[i]);
}
// Funtion that implements Dijkstra's single source shortest path
// algorithm for a graph represented using adjacency matrix
// representation
void DJ(int G[][], int src)
{
int dist[] = new int[V]; // The output array. dist[i] will hold
// the shortest distance from src to i
// sptSet[i] will true if vertex i is included in shortest
// path tree or shortest distance from src to i is finalized
Boolean sptSet[] = new Boolean[V];
// Initialize all distances as INFINITE and stpSet[] as false
for (int i = 0; i < V; i++)
{
dist[i] = Integer.MAX_VALUE;
sptSet[i] = false;
}
// Distance of source vertex from itself is always 0
dist[src] = 0;
// Find shortest path for all vertices
for (int count = 0; count < V-1; count++)
{
// Pick the minimum distance vertex from the set of vertices
// not yet processed. u is always equal to src in first
// iteration.
int u = minDistance(dist, sptSet);
// Mark the picked vertex as processed
sptSet[u] = true;
// Update dist value of the adjacent vertices of the
// picked vertex.
for (int v = 0; v < V; v++)
// Update dist[v] only if is not in sptSet, there is an
// edge from u to v, and total weight of path from src to
// v through u is smaller than current value of dist[v]
if (!sptSet[v] && G[u][v]!=0 &&
dist[u] != Integer.MAX_VALUE &&
dist[u]+G[u][v] < dist[v])
dist[v] = dist[u] + G[u][v];
}
// print the constructed distance array
printSP(dist, V);
}
// Driver method
public static void main (String[] args)
{
//If you want directly from adjecency matrix
/* int G[][] = new int[][]{{0, 16, 0, 2, 3},
{0, 0, 5, 0, 0},
{0, 3, 0, 0, 0},
{0, 12, 0, 0, 7},
{0, 10, 4, 5, 0}
};
*/
Scanner reader = new Scanner(new File("ints.txt"));
int s,d,l; //source dest and length
int i = reader.nextInt();
int G[][]=new int[i][i];
V=i; //Number of nodes
i = reader.nextInt(); //ignore nuber of edges
while (reader.hasNext()){
s = reader.nextInt();
d = reader.nextInt();
l = reader.nextInt();
G[s][d]=l;
System.out.println(i);
}
DjShortPath t = new DjShortPath();
t.DJ(G, 0);
}
}
Input:
Sample input:
5 10
0 1 16
0 3 2
0 4 3
1 2 5
2 1 3
3 1 12
3 4 7
4 1 10
4 2 4
4 3 5
Output:
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.