Dijkstra em JAVA

2 respostas
java
D

Olá. Estou desenvolvendo um grafo, utilizando como representação do mesmo uma matriz de adjacência. Segue código:

String fileName = "C:\\Users\\MATEUS\\Documents\\R\\dados\\generosFinal.csv"; //LOCAL ONDE ESTÁ O ARQUIVO
    BufferedReader in = new BufferedReader(new FileReader(fileName));
    StringBuffer sb = new StringBuffer((int) new File(fileName).length());

    String linha = in.readLine();

    while (linha != null) {
        sb.append(linha + "\n");
        linha = in.readLine();
    }

    in.close();
    String text = sb.toString();
    ArrayList<String> generos = new ArrayList<String>();

    int n = 1228;

    String lines[] = text.split("\n");

    for (int i = 0; i < n; i++) {
        lines[i] = lines[i].replace("{", "");
        lines[i] = lines[i].replace("}", "");

        String temp[] = lines[i].split(";");
        String current = temp[0];
        generos.add(temp[0]);
        lines[i] = lines[i].replace(temp[0], generos.indexOf(current) + "");

        if (temp[1].contains(",")) {
            String temp2[] = temp[1].split(",");
            for (int j = 0; j < temp2.length; j++) {

                if (!generos.contains(temp2[j])) {
                    generos.add(temp2[j]);
                }

                lines[i] = lines[i].replace(temp2[j], generos.indexOf(temp2[j]) + "");
            }
        } else {
            if (!generos.contains(temp[1]) && !temp[1].equals("NULL")) {
                generos.add(temp[1]);
                lines[i] = lines[i].replace(temp[1], generos.indexOf(temp[1]) + "");
            } else if (!temp[1].equals("NULL")) {
                lines[i] = lines[i].replace(temp[1], generos.indexOf(temp[1]) + "");
            }
        }
    }

    System.out.println("Total: " + generos.size());
    int adj[][] = new int[generos.size()][generos.size()];
    for (int i = 0; i < n; i++) {
        System.out.println(lines[i]);
    }

    for (int i = 0; i < n; i++) {
        String temp[] = lines[i].split(";");

        if (temp[1].contains(",")) {
            String temp2[] = temp[1].split(",");
            for (int j = 0; j < temp2.length; j++) {
                adj[Integer.parseInt(temp[0])][Integer.parseInt(temp2[j])] = 1;

            }
        } else {
            if (!temp[1].equals("NULL")) {
                adj[Integer.parseInt(temp[0])][Integer.parseInt(temp[1])] = 1;
            }
        }
    }

    for (int i = 0; i < adj.length; i++) {
        for (int j = 0; j < adj.length; j++) {
            if (adj[i][j] == 1) {
                System.out.println(generos.get(j) + " é subgênero de " + generos.get(i));

            }
        }
    }

    //Inicializando o Dijkstra
    int dt[] = new int[adj.length]; //Vetor para armazenar distâncias do vertice inicial aos demais
    dt[0] = 0; // Vertice inicial com distância zero
    int rot[] = new int[adj.length]; //Vetor para armazenar o índice anterior ao vertice i
    rot[0] = 0; // Vertice inicial não possui anterior
    int abertos[] = new int[adj.length]; //Vetor de vértices abertos
    boolean fechados[] = new boolean[adj.length]; //Vetor de vértices fechados
    int contFechados = 0;
    int ancora, infinito;
    infinito = 1000000;

    for (int i = 1; i < adj.length; i++) {
        dt[i] = infinito; //Atribuindo um valor "infinito" para a distância de todos os vértices
        rot[i] = 0; //Zerando o índice anterior dos vertices
        abertos[i - 1] = i - 1; //Armazena os vértices.
        fechados[i - 1] = false; //Simbolizando que o vertice está fechado
    }

    while (contFechados < adj.length) {
        
    }

Preciso desenvolver um algoritmo de menor caminho (Estou utilizando o dijkstra). Estou utilizando um “passo-a-passo” que achei em um slide, porém cheguei a um ponto no qual não estou entendendo o que fazer. Segue arquivo do slide: Slide Dijkstra
A parte que estou “enganxado” está na página 10, linha 9.
Se alguém puder me ajudar, agradeço.

2 Respostas

PedreiroDeSoftware

Por curiosidade,
Vc sabe resolver olhando um grafo relativamente simples?
Pra resolver esse algoritmo vc deve saber como ele se comporta.

juniorsatanas
Criado 2 de fevereiro de 2020
Ultima resposta 4 de fev. de 2020
Respostas 2
Participantes 3