Surya is a student at KL University, He is currently standing in the C-Block. He has 8 friends who are situated at different Blocks (Places) inside the university and he wishes to talk to each of them in person. The distances are represented on the undirected graph which is provided below. He wishes to take the shortest distance for each place from his location.
Help him in meeting every one of his friends by developing a program that can determine the shortest distance between the C-Block and every other place on the graph. Remember that the path is not required.
Hint: Use Dijkstra’s algorithm to calculate the distances between the C-Block and every other place
Output
Vertex
Distance from Source
C Block 0
FED Block 4
S Block 12
Main Canteen 19
Entrance 21
Xerox 11
R&D Block 9
Mech Block 8
Library 14job_sequencing.java
import java.util.*;
class Job {
char id;
int deadline, profit;
public Job() {
}
public Job(char id, int deadline, int profit) {
this.id = id;
this.deadline = deadline;
this.profit = profit;
}
void printJobScheduling(ArrayList<Job> arr, int t) {
int n = arr.size();
Collections.sort(arr, (a, b) -> b.profit - a.profit);
boolean result[] = new boolean[t];
char job[] = new char[t];
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = Math.min(t - 1, arr.get(i).deadline - 1); j >= 0; j--) {
if (result[j] == false) {
result[j] = true;
job[j] = arr.get(i).id;
sum += arr.get(i).profit;
break;
}
}
}
System.out.println(sum);
for (char jb : job) {
System.out.print(jb + " ");
}
System.out.println();
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
char[] jobs = new char[n];
int[] times = new int[n];
int[] profits = new int[n];
for (int i = 0; i < n; i++) {
jobs[i] = sc.next().charAt(0);
}
for (int i = 0; i < n; i++) {
times[i] = sc.nextInt();
}
for (int i = 0; i < n; i++) {
profits[i] = sc.nextInt();
}
ArrayList<Job> arr = new ArrayList<Job>();
for (int i = 0; i < n; i++)
arr.add(new Job(jobs[i], times[i], profits[i]));
Job job = new Job();
job.printJobScheduling(arr, n);
sc.close();
}
}Distance from c block
class ShortestPath {
static final int V = 9;
int minDistance(int dist[], Boolean sptSet[]) {
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;
}
void printSolution(int dist[], String[] places) {
System.out.println("Vertex \t\t Distance from Source");
for (int i = 0; i < V; i++)
System.out.println(places[i] + " \t\t " + dist[i]);
}
void dijkstra(int graph[][], int src, String[] places) {
int dist[] = new int[V];
Boolean sptSet[] = new Boolean[V];
for (int i = 0; i < V; i++) {
dist[i] = Integer.MAX_VALUE;
sptSet[i] = false;
}
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printSolution(dist, places);
}
public static void main(String[] args) {
int graph[][] = new int[][] { { 0, 4, 0, 0, 0, 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, 0, 0 }, { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 }, { 0, 0, 0, 0, 0, 2, 0, 1, 6 }, { 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
String[] places = { "C Block", "FED Block", "S Block", "Main Canteen", "Entrance", "Xerox shop", "R&D Block",
"Mech Block", "Library" };
ShortestPath t = new ShortestPath();
t.dijkstra(graph, 0, places);
}
}