0

Estou com problema para ler o arquivo dist1.txt e conseguir passar os valores de cada linha e passar para uma matriz da outra classe.

O arquivo tem o seguinte formato .txt:

1;1;00
1;2;14
1;3;05
1;4;05
1;5;12
1;6;15
2;1;14
2;2;00
2;3;07
2;4;08
2;5;09
2;6;10
3;1;05
3;2;07
3;3;00
3;4;12
3;5;21
3;6;14
4;1;05
4;2;08
4;3;12
4;4;00
4;5;15
4;6;16
5;1;12
5;2;09
5;3;21
5;4;16
5;5;00
5;6;02
6;1;15
6;2;10
6;3;14
6;4;16
6;5;02
6;6;00

Essa é a minha classe principal.

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {

    private static File file;
    static Graph subway = new Graph(6);
    static int[][] a = new int[6][6];
    private static final int S1 = 1;
    private static final int S2 = 6;

    /***
     * <h1>Metodo de leitura de arquivos</h1>
     * @param filePath - caminho absoluto do arquivo no sistema
     * @return - Para este caso, retorna uma matriz 6 x 6 somente com o peso de cada rota
     */
    public static void main(String[] args) {

      System.out.println("Desenvolvido por Guilherme alves vieria dos santos");
      System.out.println("--------------------------------------------------");
      System.out.print("Digite o nome do arquivo: ");
      System.out.println();

      Scanner in = new Scanner(System.in);
      String arquivo = in.next();

        Main.file = new File(arquivo);

        try {
            Scanner sc = new Scanner(Main.file);
            for (int i = 0; i < a.length; i++) {
                for (int j = 0; j < a.length; j++) {
                    String[] dadosLinha = sc.nextLine().split(";");
                    a[i][j] = Integer.parseInt(dadosLinha[2]);


//O problema parece que está aqui 
subway.makeEdge(Integer.parseInt(dadosLinha[0]),Integer.parseInt(dadosLinha[1]),Integer.parseInt(dadosLinha[2]));

                  }
            }
            sc.close();
            //return a;
        } catch (FileNotFoundException e) {
            System.out.println("Arquivo nao encontrado, verifique se o caminho do arquivo esta correto");
        } 

        while (true) {
            //int source = readStation("source", in);
            //int destination = readStation("destination", in);

            System.out.println("Caminho mais rapido:");
            for (Integer station : subway.path(1/*source*/, 6/*destination*/)) {
                System.out.println((station+1) + " -> ");
            }
            System.out.println("EXIT");
        }
    }

    private static int readStation(String type, Scanner in) {

      while (true) {
           System.out.println(type + ":");
           String line = in.nextLine().trim();
           if (line.isEmpty()) {
               System.out.println("Linha vazia!");
               System.exit(0);
           }
           try {
               int station = Integer.parseInt(line);
               if (station >= 1 && station <= 6) return station-1;
           } catch (NumberFormatException e) {
           }
           System.out.println("Invalid station! Try again.");
       }
     }
}

A minha outra classe é o Graph que faço a lógica para fazer a leitura do grafo.

import java.util.*;

public class Graph {
    private static final int UNDEFINED = -1;
    private int vertices[][];

    public Graph(int numVertices) {
        vertices = new int[numVertices][numVertices];
    }

    public void makeEdge(int vertex1, int vertex2, int time) {
        vertices[vertex1][vertex2] = time;
        vertices[vertex2][vertex1] = time;
    }

    public void removeEdge(int vertex1, int vertex2) {
        vertices[vertex1][vertex2] = 0;
        vertices[vertex2][vertex1] = 0;
    }

    public int getCost(int vertex1, int vertex2) {
        return vertices[vertex1][vertex2];
    }

    /**
     * @param vertex Origin vertex
     * @return a list with the index of all vertexes connected to the given vertex.
     */
    public List<Integer> getNeighbors(int vertex) {
        List<Integer> neighbors = new ArrayList<>();
        for (int i = 0; i < vertices[vertex].length; i++)
            if (vertices[vertex][i] > 0) {
                neighbors.add(i);
            }

        return neighbors;
    }

    /**
     * Implementation of the Dijkstra's algorithm.
     * @param from Source node
     * @param to Destionation node
     * @return The path.
     */
    public List<Integer> path(int from, int to) {
        //Initialization
        //--------------
        int cost[] = new int[vertices.length];
        int prev[] = new int[vertices.length];
        Set<Integer> unvisited = new HashSet<>();

        //The initial node has cost 0 and no previous vertex
        cost[from] = 0;

        //All other nodes will have its cost set to MAXIMUM and undefined previous
        for (int v = 0; v < vertices.length; v++) {
            if (v != from) {
                cost[v] = Integer.MAX_VALUE;
            }
            prev[v] = UNDEFINED;
            unvisited.add(v);
        }

        //Graph search
        //------------
        while (!unvisited.isEmpty()) {
            int near = closest(cost, unvisited);
            unvisited.remove(near);

            for (Integer neighbor : getNeighbors(near)) {
                int totalCost = cost[near] + getCost(near, neighbor);
                if (totalCost < cost[neighbor]) {
                    cost[neighbor] = totalCost;
                    prev[neighbor] = near;
                }
            }
            //Found?
            if (near == to) {
                return makePathList(prev, near);
            }
        }

        //No path found
        return Collections.emptyList();
    }

    private int closest(int[] dist, Set<Integer> unvisited) {
        double minDist = Integer.MAX_VALUE;
        int minIndex = 0;
        for (Integer i : unvisited) {
            if (dist[i] < minDist) {
                minDist = dist[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

    private List<Integer> makePathList(int[] prev, int u) {
        List<Integer> path = new ArrayList<>();
        path.add(u);
        while (prev[u] != UNDEFINED) {
            path.add(prev[u]);
            u = prev[u];
        }
        Collections.reverse(path);
        return path;
    }
}
1

1 Resposta 1

2

O problema é que no arquivo você considera que os nós são numerados de 1 a 6 enquanto que utiliza os índices numerados de 0 a 5. Até há alguns lugares onde você usa +1 ou -1 por causa disso, mas não usa em todos os lugares que deveria. Utilizando verificações nos parâmetros de Graph isso ficaria óbvio.

No entanto, há mais umas outras coisinhas que poderiam ser melhoradas no seu código. Em especial que variáveis globais são ruins, que não tem porque usar System.exit e você tem javadoc mal-formado. E também é muito mais fácil ler todas as linhas do arquivo usando o método Files.readAllLines(Path).

Eis o código revisado:

import java.io.File;
import java.io.FileNotFoundException;
import java.nio.file.Files;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Graph subway = new Graph(6);

        System.out.println("Desenvolvido por Guilherme alves vieria dos santos");
        System.out.println("--------------------------------------------------");
        System.out.println("Digite o nome do arquivo: ");

        Scanner in = new Scanner(System.in);
        String arquivo = in.next();

        try {
            for (String linha : Files.readAllLines(new File(arquivo).toPath())) {
                String[] dadosLinha = linha.split(";");
                if (dadosLinha.length != 3) throw new IllegalArgumentException();
                int a = Integer.parseInt(dadosLinha[0]);
                int b = Integer.parseInt(dadosLinha[1]);
                int c = Integer.parseInt(dadosLinha[2]);
                subway.makeEdge(a - 1, b - 1, c - 1);
            }
        } catch (FileNotFoundException e) {
            System.out.println("Arquivo não encontrado, verifique se o caminho do arquivo está correto.");
            return;
        } catch (IllegalArgumentException e) {
            System.out.println("O arquivo contém dados malformados.");
            return;
        }

        while (true) {
            //int source = readStation("source", in);
            //int destination = readStation("destination", in);

            System.out.println("Caminho mais rápido: ");
            for (Integer station : subway.path(0/*source*/, 5/*destination*/)) {
                System.out.println((station + 1) + " -> ");
            }
            System.out.println("EXIT");
        }
    }

    private static int readStation(String type, Scanner in) {
        while (true) {
            System.out.println(type + ": ");
            String line = in.nextLine().trim();
            try {
                int station = Integer.parseInt(line);
                if (station >= 1 && station <= 6) return station - 1;
            } catch (NumberFormatException e) {
                // Ignora.
            }
            System.out.println("Invalid station! Try again.");
        }
    }
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Graph {
    private static final int UNDEFINED = -1;
    private int vertices[][];

    public Graph(int numVertices) {
        if (numVertices < 0) throw new IllegalArgumentException();
        vertices = new int[numVertices][numVertices];
    }

    private void checkVertex(int vertex) {
        if (vertex < 0 || vertex >= vertices.length) throw new IllegalArgumentException();
    }

    public void makeEdge(int vertex1, int vertex2, int time) {
        checkVertex(vertex1);
        checkVertex(vertex2);
        if (time < 0) throw new IllegalArgumentException();
        vertices[vertex1][vertex2] = time;
        vertices[vertex2][vertex1] = time;
    }

    public void removeEdge(int vertex1, int vertex2) {
        checkVertex(vertex1);
        checkVertex(vertex2);
        vertices[vertex1][vertex2] = 0;
        vertices[vertex2][vertex1] = 0;
    }

    public int getCost(int vertex1, int vertex2) {
        checkVertex(vertex1);
        checkVertex(vertex2);
        return vertices[vertex1][vertex2];
    }

    /**
     * @param vertex Origin vertex
     * @return a list with the index of all vertexes connected to the given vertex.
     */
    public List<Integer> getNeighbors(int vertex) {
        checkVertex(vertex);
        List<Integer> neighbors = new ArrayList<>();
        for (int i = 0; i < vertices[vertex].length; i++) {
            if (vertices[vertex][i] > 0) {
                neighbors.add(i);
            }
        }

        return neighbors;
    }

    /**
     * Implementation of the Dijkstra's algorithm.
     * @param from Source node
     * @param to Destionation node
     * @return The path.
     */
    public List<Integer> path(int from, int to) {
        checkVertex(from);
        checkVertex(to);
        //Initialization
        //--------------
        int cost[] = new int[vertices.length];
        int prev[] = new int[vertices.length];
        Set<Integer> unvisited = new HashSet<>();

        //All other nodes will have its cost set to MAXIMUM and undefined previous
        for (int v = 0; v < vertices.length; v++) {
            cost[v] = Integer.MAX_VALUE;
            prev[v] = UNDEFINED;
            unvisited.add(v);
        }

        //The initial node has cost 0 and no previous vertex
        cost[from] = 0;

        //Graph search
        //------------
        while (!unvisited.isEmpty()) {
            int near = closest(cost, unvisited);
            unvisited.remove(near);

            for (Integer neighbor : getNeighbors(near)) {
                int totalCost = cost[near] + getCost(near, neighbor);
                if (totalCost < cost[neighbor]) {
                    cost[neighbor] = totalCost;
                    prev[neighbor] = near;
                }
            }
            //Found?
            if (near == to) {
                return makePathList(prev, near);
            }
        }

        //No path found
        return Collections.emptyList();
    }

    private int closest(int[] dist, Set<Integer> unvisited) {
        double minDist = Integer.MAX_VALUE;
        int minIndex = 0;
        for (Integer i : unvisited) {
            if (dist[i] < minDist) {
                minDist = dist[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

    private List<Integer> makePathList(int[] prev, int u) {
        List<Integer> path = new ArrayList<>();
        path.add(u);
        while (prev[u] != UNDEFINED) {
            path.add(prev[u]);
            u = prev[u];
        }
        Collections.reverse(path);
        return path;
    }
}
1

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .