Question

Please Provide the solution in java, already have a question which is answer in C++.

Language: java.

Please don't provide your email for private answer.

Q1. Implement a program which allows the user to find the shortest path between two nodes in a graph possibly passing through a third node. I.e. the user should be able to ask questions like: Which is the shortest path from A to B passing through C? The program should output an ordered list of the nodes to traverse from A to B if such a path exists. If no such path exists then the program should output that no such path exists.

Use sample text provided below as input when not executing tests (in the case that the tests should be executed you may use another input). This is the undirected road network of New York City. It is connected, contains parallel edges, but no self-loops. The edge weights are travel times and are strictly positive. You should also calculate/show the time complexity of your algorithm.

Sample Text file:

264346
733846
1 2 2008
2 1 2008
3 4 395
4 3 395
5 6 1935
6 5 1935
7 8 3828
8 7 3828
9 10 4182
10 9 4182
9 11 3500
11 9 3500
1 12 2105
12 1 2105
2 13 1478
13 2 1478
14 15 3427
15 14 3427
16 17 4148
17 16 4148
18 19 2529
19 18 2529
20 21 3065
21 20 3065
20 22 3163
22 20 3163
23 24 6768
24 23 6768
25 26 1300
26 25 1300
27 28 1957
28 27 1957
29 30 1295
30 29 1295
31 32 8530
32 31 8530
33 34 4986
34 33 4986
33 35 843
35 33 843
36 37 908
37 36 908
38 39 2545
39 38 2545
40 41 980
41 40 980
29 42 2686
42 29 2686
43 44 1425
44 43 1425
44 45 4410
45 44 4410
46 47 2759
47 46 2759
2 48 1541
48 2 1541
49 50 3787
50 49 3787
49 51 2964
51 49 2964
52 53 5170
53 52 5170
54 55 1300
55 54 1300
56 57 1834
57 56 1834
58 59 1762
59 58 1762
60 61 1253
61 60 1253
62 63 6045
63 62 6045
64 65 2578
65 64 2578
66 58 1527
58 66 1527
67 68 8081
68 67 8081
68 60 793
60 68 793
60 69 4270
69 60 4270
70 71 883
71 70 883
69 70 1136
70 69 1136
72 73 12904
73 72 12904
74 75 1995
75 74 1995
74 76 3516
76 74 3516
77 78 1220
78 77 1220
77 79 2327
79 77 2327
78 80 11763
80 78 11763
78 81 3209
81 78 3209
82 83 922
83 82 922
82 84 4359
84 82 4359
85 86 19802

Answer 1

There is problem with your question aa you didn't provided edges of you need to change edges and input that you know I have shown the solution using my own graph and an edge so you just need to change those that's it and everything remains same.

Code

import java.io.*; 

import java.util.*; 

import java.util.LinkedList; 

  
class Graph 
{ 

    private int V;   // No. of vertices 

    private LinkedList<Integer> adj[]; //Adjacency List 

  

    //Constructor 

    Graph(int v) 

    { 

        V = v; 

        adj = new LinkedList[v]; 

        for (int i=0; i<v; ++i) 

            adj[i] = new LinkedList(); 

    } 

  

    //Function to add an edge into the graph 

    void addEdge(int v,int w)  {   adj[v].add(w);   } 

  

    //prints BFS traversal from a given source s 

    Boolean isReachable(int s, int d) 

    { 

        LinkedList<Integer>temp; 

  

        // Mark all the vertices as not visited(By default set 

        // as false) 

        boolean visited[] = new boolean[V]; 

  

        // Create a queue for BFS 

        LinkedList<Integer> queue = new LinkedList<Integer>(); 

  

        // Mark the current node as visited and enqueue it 

        visited[s]=true; 

        queue.add(s); 

  

        // 'i' will be used to get all adjacent vertices of a vertex 

        Iterator<Integer> i; 

        while (queue.size()!=0) 

        { 

            // Dequeue a vertex from queue and print it 

            s = queue.poll(); 

  

            int n; 

            i = adj[s].listIterator(); 

  

            // Get all adjacent vertices of the dequeued vertex s 

            // If a adjacent has not been visited, then mark it 

            // visited and enqueue it 

            while (i.hasNext()) 

            { 

                n = i.next(); 

  

                // If this adjacent node is the destination node, 

                // then return true 

                if (n==d) 

                    return true; 

  

                // Else, continue to do BFS 

                if (!visited[n]) 

                { 

                    visited[n] = true; 

                    queue.add(n); 

                } 

            } 

        } 

  

        // If BFS is complete without visited d 

        return false; 

    } 

  
    public static void main(String args[]) 

    { 

        // Create a graph given in the above diagram 

        Graph g = new Graph(4); 

        g.addEdge(0, 1); 

        g.addEdge(0, 2); 

        g.addEdge(1, 2); 

        g.addEdge(2, 0); 

        g.addEdge(2, 3); 

        g.addEdge(3, 3); 

  

        int u = 1; 

        int v = 3; 

        if (g.isReachable(u, v)) 

            System.out.println("There is a path from " + u +" to " + v); 

        else

            System.out.println("There is no path from " + u +" to " + v);; 

  

        u = 3; 

        v = 1; 

        if (g.isReachable(u, v)) 

            System.out.println("There is a path from " + u +" to " + v); 

        else

            System.out.println("There is no path from " + u +" to " + v);; 

    } 
} 

SCREENSHOT