Algoritmo de dijkstra recebendo um arquivo

2 respostas
E

Olá galera,

estou com dificuldade na resolução de um exercício. para este caso abaixo, é melhor eu usar stream ou filewriter?!
Como eu pego o valor de 1 por 1? para eu poder atribuir as variáveis? Alguém me dá uma luz plz!

Escreva um programa que receba pela linha de comando o nome de um arquivo (contendo a descrição de um digrafo). O arquivo fornecido ao programa deverá ter o seguinte layout:

n m s t
u1 v1 c1
u2 v2 c2

um vm cm

onde n é a quantidade de vértices, m a quantidade de arcos, s é o vértice origem, t é o vértice destino, ui e vi são a origem e o destino do arco i e ci é o custo da aresta i. Por exemplo, para o digrafo abaixo, se s = 1 e t = 4, teríamos o arquivo à direita do grafo.

2 Respostas

E

Como eu coloco que um vértice é adjacente à o outro e atrelar junto a ele um custo?

E
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;

class ep2 {
	
   public static void main(String[] args) throws IOException {
     InputStream is = new FileInputStream("arquivo.txt");
     InputStreamReader isr = new InputStreamReader(is);
     BufferedReader br = new BufferedReader(isr);
     String result = br.readLine();
     double minDistance = Double.POSITIVE_INFINITY; 
          
         System.out.println(result);
         
	     String n1 = String.valueOf(result.charAt(0));
	     String m1 = String.valueOf(result.charAt(2));
	     String s1 = String.valueOf(result.charAt(4));
	     String t1 = String.valueOf(result.charAt(6));
	     
	     int n = Integer.parseInt(n1);
	     int m = Integer.parseInt(m1);
	     int s = Integer.parseInt(s1);
	     int t = Integer.parseInt(t1);
	     
         result = br.readLine(); 
         
         int[][] V=new int[n+1][m+1];   

     while (result != null) {
         int tam = result.length();
         System.out.println(result);
         if (tam == 5){        	    
        	String x1 = String.valueOf(result.charAt(0));
        	String y1 = String.valueOf(result.charAt(2));
        	String custo = String.valueOf(result.charAt(4));
        	int x = Integer.valueOf(x1);
        	int y = Integer.valueOf(y1);
	        V[x][y] = Integer.parseInt(custo);
	        result = br.readLine();
         }
         else if (tam == 6){      	   
        	 String n2 =  String.valueOf(result.charAt(4)) + String.valueOf(result.charAt(5)) ;
        	 String x1 = String.valueOf(result.charAt(0));
        	 String y1 = String.valueOf(result.charAt(2));
        	 int x = Integer.valueOf(x1);
         	 int y = Integer.valueOf(y1);
        	 V[x][y] = Integer.parseInt(n2);
        	 result = br.readLine();
         }
         else {
        	 result = br.readLine();
         }
       }
     
       br.close();
       int aux = 99;
       int new_s = s;
       String Z = String.valueOf(t);
       while(new_s != t){
		   for (int i=1; i<=n; i++){
	    	   if (V[new_s][n] < aux){
	    		   aux = V[new_s][n]; 
	    		   new_s = n;	    		   
	    	   }
	       }
		   Z += String.valueOf(new_s);
		   minDistance += aux; 
		   aux = 99;
       }
       System.out.println("Caminho mínimo do vértice "+s+" para o vértice "+t+" : " + Z);
       System.out.println("Custo:" + minDistance);

   }
 }

Olá colegas, o código está sem erros(de sintaxe), mas esses dois últimos sysout's não estão sendo impressos, alguém sabe pq?

ah, eu queria fazer uma condição tipo assim if (V[new_s][n] != null), mas não posso equiparar nada com NULL na matriz, alguém tem ideia de como fazê-lo? obg

Criado 18 de abril de 2014
Ultima resposta 21 de abr. de 2014
Respostas 2
Participantes 1