public static Percurso shortestPathTransbordoNaoClone(Graph <Cais , Linha> g , Cais caisInicio , Cais caisFim , int instanteInicial ){
        LinkedList <Cais> listaCais = new LinkedList <> ();
        AlgoritmosMap2.shortestPathTransbordos(g, caisInicio, caisFim, listaCais);
        System.out.println(listaCais.size());
          return new Percurso (listaCais , instanteInicial);
    }


    //shortest-path between vOrig and vDest
    public static <V, E> double shortestPathTransbordos(Graph<Cais, Linha> g, Cais vOrig, Cais vDest, LinkedList<Cais> shortPath) {
        if (!g.validVertex(vDest) || !g.validVertex(vOrig)) {
            return 0;
        } else if (g.getKey(vDest) == g.getKey(vOrig)) {
            shortPath.add(vDest);
            return 1;
        }
//        int nverts = g.numVertices();
//        boolean[] visited = new boolean[nverts]; //default value: false
//        int[] pathKeys = new int[nverts];
//        double[] dist = new double[nverts];
//        V[] vertices = g.allkeyVerts();
//        shortestPathLength(g, vOrig, vertices, visited, pathKeys, dist);
//        int dest = g.getKey(vDest);
//        getPath(g, vOrig, vDest, vertices, pathKeys, shortPath);
//
//        return dist [dest];
//
        shortPath.clear();
        ArrayList<LinkedList<Cais>> paths = new ArrayList<>();
        ArrayList<Double> dists = new ArrayList<>();
        shortestPathsTransbordos(g, vOrig, paths, dists,vDest);

//        for (Double dist : dists) {
//            System.out.println(dist);
//        }
        //   System.out.println("\n");
        for (LinkedList<Cais> path : paths) {
            if (path.size() > 2) {
                if (g.getKey(path.getFirst()) == g.getKey(vOrig) && g.getKey(vDest) == g.getKey(path.getLast())) {
                    for (Cais v : path) {
                        shortPath.add(v);
                    }

                    return dists.get(paths.indexOf(path));
                }
            }
        }
        return 0;
    }

 //shortest-path between voInf and all other
    public static <V, E> boolean shortestPathsTransbordos(Graph<Cais, Linha> g, Cais vOrig, ArrayList<LinkedList<Cais>> paths, ArrayList<Double> dists,Cais VDest) {

        if (!g.validVertex(vOrig)) {
            return false;
        }

        int nverts = g.numVertices();
        boolean[] visited = new boolean[nverts]; //default value: false
        int[] pathKeys = new int[nverts];
        double[] dist = new double[nverts];
        Cais[] vertices = g.allkeyVerts();

        for (int i = 0; i < nverts; i++) {
            dist[i] = Double.MAX_VALUE;
            pathKeys[i] = -1;
        }

        AlgoritmosMap2.shortestPathTransbordosMethod(g, vOrig, vertices, visited, pathKeys, dist,vOrig,VDest);

        dists.clear();
        paths.clear();
        for (int i = 0; i < nverts; i++) {
            paths.add(null);
            dists.add(null);
        }
        for (int i = 0; i < nverts; i++) {
            LinkedList<Cais> shortPath = new LinkedList<>();
            if (dist[i] != Double.MAX_VALUE) {
                getPath(g, vOrig, vertices[i], vertices, pathKeys, shortPath);
            }
            paths.set(i, shortPath);
            dists.set(i, dist[i]);
        }
        return true;
    }
 protected static <V, E> void shortestPathTransbordosMethod(Graph<Cais, Linha> g, Cais vOrig, Cais[] vertices,
            boolean[] visited, int[] pathKeys, double[] dist,Cais caisog,Cais caisdes) {

        for (Cais vertice : g.vertices()) {
            dist[g.getKey(vOrig)] = Double.MAX_VALUE;
            pathKeys[g.getKey(vOrig)] = -1;
            visited[g.getKey(vOrig)] = false;
        }
        dist[g.getKey(vOrig)] = 0;
        while (vOrig != null) {
//                    while(g.getKey(vOrig)!= -1){

            visited[g.getKey(vOrig)] = true;
            for (Cais adjVertice : g.adjVertices(vOrig)) {

                Edge<Cais,Linha> edge = g.getEdge(vOrig, adjVertice);
                double aux=edge.getWeight();
                if (!((edge.getVOrig().getEstacao().getNomeEstacao().equals(caisog.getEstacao().getNomeEstacao()))&&(edge.getVDest().getEstacao().getNomeEstacao().equals(caisog.getEstacao().getNomeEstacao())))) {
                    if (!((edge.getVOrig().getEstacao().getNomeEstacao().equals(caisdes.getEstacao().getNomeEstacao()))&&(edge.getVDest().getEstacao().getNomeEstacao().equals(caisdes.getEstacao().getNomeEstacao())))) {
                       if (edge.getElement().getIdentificacao().equals("0")) {
                    aux=TRANSBORDO_HIGH_VALUE;
                }
                }

                }
                if (!visited[g.getKey(adjVertice)] && dist[g.getKey(adjVertice)] > dist[g.getKey(vOrig)] + aux) {
                    dist[g.getKey(adjVertice)] = dist[g.getKey(vOrig)] + aux;
                    pathKeys[g.getKey(adjVertice)] = g.getKey(vOrig);
                }
            }
            vOrig = getVertMinDist(g, dist, visited);
        }
    }