Cisco Online test (Hard Level)
PankajTiwari
3687
Interview

* 1. You have to find the all shortest path between two node in undirected weighted graph .You have to find the all shortest path between two node in undirected weighted graph .You have to find the all shortest path between two node in undirected weighted graph .You have to find the all shortest path between two node in undirected weighted graph .``

Check the document attached :
My solution did not worked correctly becuase i was out of time :
Provide better solution if some any body can :
import java.io.;
import java.math.;
import java.security.;
import java.text.;
import java.util.;
import java.util.concurrent.;
import java.util.function.;
import java.util.regex.;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

/*
 * Complete the 'classifyEdges' function below.
 *
 * The function is expected to return a STRING_ARRAY.
 * The function accepts WEIGHTED_INTEGER_GRAPH g as parameter.
 */

/*
 * For the weighted graph, <name>:
 *
 * 1. The number of nodes is <name>Nodes.
 * 2. The number of edges is <name>Edges.
 * 3. An edge exists between <name>From[i] and <name>To[i]. The weight of the edge is <name>Weight[i].
 *
 */

public static void find(Stack<Integer> stackEdges, boolean[] visited, int currNode, int tNode, int currWeight, List<Integer> gFrom, List<Integer> gTo, List<Integer> gWeight){
    if(currWeight>minWeight)
       return;
    if(currNode == tNode){
        if(currWeight<minWeight){
            minWeight=currWeight;
            lsRes.clear();
            lsRes.add(copy(stackEdges));
        }else if(currWeight == minWeight){
            lsRes.add(copy(stackEdges));
        }
        stackEdges.pop();
        return;
    }
    for(int i=0;i<gFrom.size();i++){
        if(gFrom.get(i)==currNode && !visited[gTo.get(i)]){
            stackEdges.push(i);
            visited[gTo.get(i)]=true;
            find(stackEdges, visited, gTo.get(i), tNode, currWeight+gWeight(i), gFrom, gTo, gWeight);
            visited[gTo.get(i)]=false;
            stackEdges.pop();
        }else if(gTo.get(i)==currNode && !visited[gFrom.get(i)]){
            stackEdges.push(i);
            visited[gFrom.get(i)]=true;
            find(stackEdges, visited, gFrom.get(i), tNode, currWeight+gWeight(i), gFrom, gTo, gWeight);
            visited[gFrom.get(i)]=false;
            stackEdges.pop();
        }
    }
}
static Stack<Integer> copy (Stack<integer> stack){
    Stack<Integer> ns = new Stack<>();
    for(int i=0;i<stack.capacity();i++)
    ns.push(stack.get(i));
    return ns;
}


static int minWeight = Integer.MAX_VALUE;
static List<Stack<Integer>> lsRes = new ArrayList<>();


public static List<String> classifyEdges(int gNodes, List<Integer> gFrom, List<Integer> gTo, List<Integer> gWeight) {
    Graph graph = new Graph(gNodes);
    for(int i=0;i<gFrom.size();i++){
        graph.addEdge(gFrom.get(i), gTo.get(i), gWeight.get(i));
    }
    Stack<Integer> stackEdges = new Stack();
    visited[1]=true;
    find(stackEdges, visited, 1, gNodes, 0, gFrom, gTo, gWeight);
    booloean[] all - new boolean[gNodes+1];
    List<String> lsRes = new ArrayList<>();

    return lsRes;
}

}
class Graph {
int noNodes = 0;
int sNode =1;
int eNode;
public int[][] dist;
public Graph(int noNodes){
this.noNodes = noNodes;
eNode = noNodes;
dist = new int[noNodes+1][noNodes+1];
for(int i =0 ;i<=noNodes;i++)
Arrays.fill(dist[i], -1);
}
public void addEdge(int no1, int no2, int d){
dist[no1][no2]=dist;
dist[no2][no1]=dist;
}
}

public class Solution {

Comments (6)