Ajuda com Implementação do Algoritmo de Floyd

Programação Java
#1

Ola para todos.
Bom eu estou tentnado implementar o algoritmo de floyd, para encontrar o menor caminho dentro do grafo mas não eu estou conseguindo
Será que alguem pode me ajudar

Eu já vi vários exemplos na internet voltados para C, mas são totalmente diferentes e dificeis de interpretar e levar para o java.
Segue um exemplo do pseudocódigo em C encontrado na wikipedia

ROTINA fw(Inteiro[1..n,1..n] grafo)
    # Inicialização
    VAR Inteiro[1..n,1..n] dist := grafo
    VAR Inteiro[1..n,1..n] pred
    PARA i DE 1 A n
        PARA j DE 1 A n
            SE dist[i,j] < Infinito ENTÃO
                pred[i,j] := i
    # Laço principal do algoritmo
    PARA k DE 1 A n
        PARA i DE 1 A n
            PARA j DE 1 A n
                SE dist[i,j] > dist[i,k] + dist[k,j] ENTÃO
                    dist[i,j] = dist[i,k] + dist[k,j]
                    pred[i,j] = pred[k,j]
RETORNE dist
#2

Grafo no pseudocodigo é uma matriz do seguinte tipo no java: int[][] grafo = new int[N][N] onde N é o número de vértices do seu grafo. Daí vc enumera seus vertices e se do vertice 3 para o vertice 5 por exemplo, existe uma aresta, você coloca o valor dessa aresta na posição grafo[3][5] por exemplo, e para aonde não existir aresta você põe -1.

dist no pseudocódigo você segue a mesma linha de raciocinio, só que aonde não existir aresta, ao invez de por -1 você poe INTEGER.MAX_VALUE.
pred mesma coisa, só que dai em todas as posições vc põe Integer.MAX_VALUE.

Depois disso é só traduzir o algoritmo pra Java e boa. O vetor dist no final da execução conterá o resultado que você quer.

#3

Olha não consegui entender muito bem.
Entretnato na minha classe o número de vertices é dado por um vetor.

Bom na Main eu estou Chamando o método através do código

			System.out.println("Digite a cidade de Origem");
			String  cidadex, cidadey;
			Scanner cidade1 = new Scanner(System.in);
			cidadex= cidade1.nextLine();
			System.out.println("Digite a cidade de Destino");
			Scanner cidade2 = new Scanner(System.in);
			cidadey= cidade2.nextLine();
	        
			g.floyd(cidadex, cidadey);

Eu queria vc dessem uma olhada na implementação do floyd, não consigo saber onde estou errando.

[code]
public class Grafo {
private int elementos;
private Vertice[] vertices;
private int[][] adj;

public Grafo(int v) {
elementos = 0;
vertices = new Vertice[v];
adj = new int[v][v];

}

//Inicio do Floyd
public int floyd(String a, String b){
// Inicialização
int dist[i][j] = adj[i][j]; //VAR Inteiro[1…n,1…n] dist := grafo
int [][] pred = new int [this.elementos][this.elementos]; // VAR Inteiro[1…n,1…n] pred

for(i=0;i<elementos;i++){
for(i=0;i<elementos;i++){
if(dist[i][j] < 99999999) {
pred[i][j] = i;
}
}
}
// Laço principal do algoritmo
for(int k=0;k<elementos;k++){
for(i=0;i<elementos;i++){
for(j=0;j<elementos;j++){
if (dist[i][j] > dist[i][k] + dist[k][j]){
dist[i][j] = dist[i][k] + dist[k][j];
pred[i][j] = pred[k][j];
return dist; // não sei o que fazer com esta linha esta dando erro
}
}
}
}[/code]

#4

[quote=Designer]
Eu queria vc dessem uma olhada na implementação do floyd, não consigo saber onde estou errando.

[code]
public class Grafo {
private int elementos;
private Vertice[] vertices;
private int[][] adj;

public Grafo(int v) {
elementos = 0;
vertices = new Vertice[v];
adj = new int[v][v];

}

//Inicio do Floyd
public int floyd(String a, String b){
// Inicialização
int dist[i][j] = adj[i][j]; //VAR Inteiro[1…n,1…n] dist := grafo
int [][] pred = new int [this.elementos][this.elementos]; // VAR Inteiro[1…n,1…n] pred

for(i=0;i<elementos;i++){
for(i=0;i<elementos;i++){
if(dist[i][j] >< 99999999) {
pred[i][j] = i;
}
}

}[/code][/quote]

Conflito de nomes de variáveis !!! (“laço for esta correto ???”)

[youtube]http://www.youtube.com/watch?v=qdY4vK1V0Nk[/youtube]

[youtube]http://www.youtube.com/watch?v=mk62s7W0kN8&feature=related[/youtube]

#5

cara olhei bem por cima aqui no seu codigo e acho que encontrei um erro

# //Inicio do Floyd public int floyd(String a, String b){ int dist[i][j] = adj[i][j]; //VAR Inteiro[1..n,1..n] dist := grafo return dist; // não sei o que fazer com esta linha esta dando erro }

Como você tá retornando uma matriz, voce tem q especificar o tipo de retorno na assinatura do método que é uma matriz.
ficaria assim:

 public int [][] floyd(String a, String b){

suponho que seja isso! =)
Abraço

#6

A minha pergunta agora é como saber se o algoritmo esta percorrendo o menor caminho ou não?
Tipo como eu devo chamar o método floyd na main?
De que forma eu devo fazer para imprimir o menor caminho?

#7

o problema era esse mesmo? da declaração de matriz?

Na Main, você nao precisa declarar tantos Scanners. Basta um:

String  cidadex, cidadey;
Scanner leitor = new Scanner (System.in);
System.out.println("Digite a cidade de Origem");  
cidadex= leitor.nextLine();
# System.out.println("Digite a cidade de Destino");  
# cidadey=leitor.nextLine();

Não sei como está o resto da sua Main, então aconselho o seguinte. Instancie um objeto do tipo grafo, e a partir dele você invoca os métodos desejados. Se o código de Floyd estiver correto, para exibir o menor caminho (matriz) é preciso que na Main exista uma matriz e que nela seja guardado o retorno do método floyd.

Grafo g1 = new Grafo(5); // suponha 5 vertices
int m1 [][]=new int[5][5];
m1 = g1.floyd(cidadex,cidadey); // m1 recebe o retorno do método floyd
for(int l=0;l<5;l++){
   for(int c=0;c<5;c++){   // lê os valores da matriz
      System.out.print(m1[ l ][ c ]+" "); 
   }
   System.out.println();
}

Não testei aqui, mas creio q vá funcionar!

Abraços

#8

[quote=Brunojti]o problema era esse mesmo? da declaração de matriz?

Na Main, você nao precisa declarar tantos Scanners. Basta um:

String  cidadex, cidadey;
Scanner leitor = new Scanner (System.in);
System.out.println("Digite a cidade de Origem");  
cidadex= leitor.nextLine();
# System.out.println("Digite a cidade de Destino");  
# cidadey=leitor.nextLine();

Não sei como está o resto da sua Main, então aconselho o seguinte. Instancie um objeto do tipo grafo, e a partir dele você invoca os métodos desejados. Se o código de Floyd estiver correto, para exibir o menor caminho (matriz) é preciso que na Main exista uma matriz e que nela seja guardado o retorno do método floyd.

Grafo g1 = new Grafo(5); // suponha 5 vertices
int m1 [][]=new int[5][5];
m1 = g1.floyd(cidadex,cidadey); // m1 recebe o retorno do método floyd
for(int l=0;l<5;l++){
   for(int c=0;c<5;c++){   // lê os valores da matriz
      System.out.print(m1[ l ][ c ]+" "); 
   }
   System.out.println();
}

Não testei aqui, mas creio q vá funcionar!

Abraços

[/quote]

Floyd esta desta forma no código

[code] public int [][] floyd2 (String a, String b){
//ROTINA fw(Inteiro[1…n,1…n] grafo)
int i,k,j;

	int dist [][] = new int[this.elementos][this.elementos];
	int [][]pred = new int[this.elementos][this.elementos];
	int aux [][] = new int[this.elementos][this.elementos];
   // VAR Inteiro[1..n,1..n] pred;
    for(i=0;i<this.elementos;i++){ 
        for(j=0;j<this.elementos;j++){
        	dist[i][j] = this.adj[i][j];
        	if (dist[i][j] < Integer.MAX_VALUE) {
                pred[i][j] = i;
        	}
        }
    }
    //Laço principal do aloritmo
    for(k=0;k<this.elementos;k++){
        for(i=0;i<this.elementos;i++){ 
        	for(j= 0;j<this.elementos;j++){ 
                if( dist[i][j] > dist[i][k] + dist[k][j]){ 
                	dist[i][j] = dist[i][k] + dist[k][j];
                    pred[i][j] = pred[k][j];
                    aux[k][j]=pred[i][j]+dist[i][j];
                    //String arrayString = Arrays.deepToString( dist );
            	    //System.out.println( Arrays.deepToString( dist ) );
                    return pred;
                    //return dist.toString();//dist;
                }
   
                }
        	}
    	}
System.out.println("1");
return pred;
      }

[/code]

Chamando ele desta forma na Main e o Grafo tem 20 posições

case 4: String cidadex, cidadey; System.out.println("Digite a cidade de Origem"); Scanner leitor = new Scanner(System.in); cidadex= leitor.nextLine(); System.out.println("Digite a cidade de Destino"); cidadey= leitor.nextLine(); m1 = g.floyd2(cidadex,cidadey); // m1 recebe o retorno do método floyd for(int l=0;l<17;l++){ for(int c=0;c<17;c++){ // lê os valores da matriz System.out.print(m1[ l ][ c ]+" "); } System.out.println(""); }

O Problema que ele não esta encontrando o menor caminho ele imprimiu outra Matriz contendo estes valores

Quando coloco pra retornar dist Retorna esse conjunto de valores
0 260 170 0 0 0 0 0 0 0 0 0 0 0 0 0 0
260 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
170 0 0 80 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 80 0 0 120 0 100 0 0 0 0 0 0 0 0 0
0 0 0 150 0 70 130 0 0 0 0 0 0 0 0 0 0
0 0 0 120 70 0 0 150 200 0 0 0 0 0 0 0 0
0 0 0 0 130 0 0 0 0 70 0 0 0 0 0 0 0
0 0 0 100 0 150 0 0 80 0 0 0 0 0 0 0 0
0 0 0 0 0 200 0 80 0 160 100 0 0 0 0 0 0
0 0 0 0 0 0 70 0 160 0 160 80 0 80 0 0 0
0 0 0 0 0 0 0 0 100 160 0 0 0 80 150 200 0
0 0 0 0 0 0 0 0 0 80 0 0 70 100 0 0 0
0 0 0 0 0 0 0 0 0 0 0 70 0 0 120 0 80
0 0 0 0 0 0 0 0 0 80 80 100 0 0 110 0 0
0 0 0 0 0 0 0 0 0 0 150 0 120 110 0 140 0
0 0 0 0 0 0 0 0 0 0 200 0 0 0 140 0 0
0 0 0 0 0 0 0 0 0 0 0 0 80 0 0 0 0

Quando eu mudo para retornar o pred
Retorna isso
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 0 3 3 3 3 3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11
12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12
13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13
14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16

Eu vi que no floyd ele essa matriz mesmo contendo na coloca 1 e na 1 recebe valor 1 na coluna 1 na linha 2 recebe 1 e assim por diante

E na verdade o floyd teria que retornar o menor caminho entre 2 vertices que no caso seriam duas cidades

Se vc entra com uma cidade de origem e dentro ela seria por exemplo o vertice 1 e vc entraria com a segunda cidade que seria por exemplo o vertice 8

Ele teria que mostrar quais vertices que ele percorreu para chegar no vertice 8. Qual o menor caminho

#9 
// Now the shortest distance between i and j will be in dist[i][j]
int dist[N][N];  // For some N
int i, j, k;
// Input data into dist, where dist[i][j] is the distance from i to j.
 
   for ( k = 0; k < N; k++ )
      for ( i = 0; i < N; i++ )
         for ( j = 0; j < N; j++ )
            dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] );
#10

[code]import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//FW is short for Floyd-Warshall
public class FW_sample {

Node[] node;	// nodes
int n;			// number of nodes
Queue queue;	// the queue

int nc;			// number of customers
int[] customer;	// customers
int[][] dist;	// distance between any pair of nodes

// construct the FW with input arc file and customer file
public FW_sample(String arcfile, String customerfile){
	this.readArc(arcfile);
	this.ReadCustomer(customerfile);
}


// this method reads the information of the nodes and arcs
public void readArc(String filename){
	try{
		
		File input = new File(filename);
		BufferedReader br = 
			new BufferedReader(
					new InputStreamReader(
							new FileInputStream(input)));
		
		String line;
		String token;
		line = br.readLine();	// read the first line of the input file

		//parse the first line of the input file
		StringTokenizer st = new StringTokenizer(line);	
		token = st.nextToken();
		
		this.n = Integer.parseInt(token); // get the number of the nodes, n
		this.node = new Node[n]; // create n Nodes
		for(int i=0; i<n; i++){
			node[i] = new Node();
			node[i].num = i;
		}
		
		while((line = br.readLine())!= null){//read each rest lines in the file which contains arc information
			int from;
			int to;
			int cost;
			
			st = new StringTokenizer(line);
			token = st.nextToken();
			from = Integer.parseInt(token);
			token = st.nextToken();
			to = Integer.parseInt(token);
			token = st.nextToken();
			cost = Integer.parseInt(token);
			
			Arc arc = new Arc();
			arc.from_node = node[from];
			arc.to_node = node[to];
			arc.cost = cost;
			
			// if the node contains no arcs, this is the first out arc
			if (node[from].first_out_arc == null){
				node[from].first_out_arc = arc;
				node[from].last_out_arc = arc;
			}
			// else we should find the last arc 
			else{
				(node[from].last_out_arc).next_out_arc = arc;
				node[from].last_out_arc = arc;
			}
		}

		br.close();

	} catch (Exception e) {
		e.printStackTrace();
	}


}

// read the customers
public void ReadCustomer(String filename){
	try{
		File customerFile = new File(filename);
		BufferedReader br = new BufferedReader(
								new InputStreamReader(
									new FileInputStream(customerFile)));
		
		String temp = br.readLine();
		this.nc = Integer.parseInt(temp);
		this.customer = new int[nc];

		// this may generate exceptions if the input file is in wrong format
		for(int i=0; i><nc; i++){
			temp = br.readLine();
			customer[i] = Integer.parseInt(temp);
		}
		
	}catch(Exception e){
		e.printStackTrace();
	}
}

// print the distance between each pair of customers
public void printDist(){
	for(int i=0; i><nc; i++){
		for(int j=i; j><nc; j++){
			System.out.println(
					"The distance from customer " + i + "(node " + customer[i] + ")" +
					" to customer " + j + "(node " + customer[j] + ")" + 
					" is " + dist[customer[i]][customer[j]]);
		}
	}
}


// implement the Floyd-Warshall algorithm here:
/* sample codes */
public void floyd_Warshall(){
	this.dist = new int[n][n];
	
	for(int i=0; i><n; i++){
		for(int j=0; j><n; j++){
			if (i==j) dist[i][j] = 0;
			else dist[i][j] = 10000;
		}
	}

	for(int i=0; i><n; i++){
		Arc arc = node[i].first_out_arc;
		while(arc != null){
			dist[i][arc.to_node.num] = arc.cost;
			// here may change the graph to undirected
			//dist[arc.to_node.num][i] = arc.cost;
			arc = arc.next_out_arc;
		}
	}
	
	
	for(int k=0; k><n; k++){
		for(int i=0; i><n; i++){
			for(int j=0; j><n; j++){
				if (dist[i][j] > dist[i][k] + dist[k][j]){
					dist[i][j] = dist[i][k] + dist[k][j];
				}
			}
		}
	}
}


// this method finds the shortest path from node source to all nodes
// by FIFO algorithm
public void findPath(int source){
	for(int i=0; i<n; i++) node[i].dist = 10000;
	node[source].dist = 0;

	queue = new Queue();
	queue.addToTop(node[source]);
	
	while(!queue.isQueueEmpty()){
		
		Node t = queue.getAndRemoveTop();
		if (t==null) continue;//this should not happen if no error in the queue
		
		Arc arc = t.first_out_arc;
		while(arc!=null){
			int tmpdist = arc.to_node.dist;
			if (tmpdist > t.dist + arc.cost){
				arc.to_node.dist = t.dist + arc.cost;
				arc.to_node.pred = t;
				if (!queue.is_in_Q(arc.to_node)) queue.addToBottom(arc.to_node);
			}
			arc = arc.next_out_arc;
		}
	}
	
}

public static void main(String[] args) {
	FW_sample fw = new FW_sample("a1_data.txt", "customer.txt");
	fw.floyd_Warshall();
	fw.printDist();
	
	// the following codes print out the distance between all pairs of nodes 
	// by the FIFO algorithm, you may use this to check your result with 
	// Floyd-Warshall algorithm
	/*
	for(int i=0; i<fw.n; i++){
		fw.findPath(i);
		for(int j=0; j><fw.n; j++) 
			System.out.println(i+" to "+j+" : "+fw.node[j].dist);
		System.out.println("-------------");
	}
	*/
	
}

}

class Node{ /* node structure /
int num; / node id /
Arc first_out_arc; / first outbound arc from the node /
Arc last_out_arc; / last outbound arc from the node, you may or may not use this */
Node pred; // for shortest path
Node next; // for the queue
int dist;

public Node(){		// construciton
	this.num = -1;
	this.dist = -1;
	this.pred = null;
	this.first_out_arc = null;
	this.last_out_arc = null;
}

}

class Arc{ /* arc structure /
Node from_node; / from node of the arc /
Node to_node; / to node of the arc /
int cost; / some type of weight /
Arc next_out_arc; / next arc on the list of outbound arcs of the same from node */

public Arc(){
	this.from_node = null;
	this.to_node = null;
	this.cost = -1;
	this.next_out_arc = null;
}

}

class Queue{
Node top; // top of the queue
Node bottom; // bottom of the queue
int length; //length of the queue

public Queue(){
	this.top = null;
	this.bottom = null;
	length = 0;
}

// to check whether the queue is empty
public boolean isQueueEmpty(){
	if (length==0) return true;
	else return false;
}

// to check whether a node is in the queue
public boolean is_in_Q(Node node){
	if (node==null) return false;
	if (this.top == null || this.length == 0) return false;
	Node t = this.top;
	while(t != null){
		if (t == node) return true;
		t = t.next;
	}
	return false;
}

// add a node to the top of the queue
public void addToTop(Node node){
	if (node == null) return;
	if (this.length == 0){
		this.top = node;
		this.bottom = node;
		this.length ++;
	}
	else{
		node.next = top;
		this.top = node;
		this.length ++;
	}
}

// add a node to the bottom of the queue
public void addToBottom(Node node){
	if (node == null) return;
	if (this.length == 0){
		this.top = node;
		this.bottom = node;
		this.length ++;
	}
	else{//length>0
		this.bottom.next = node;
		this.bottom = node;
		node.next = null;
		this.length ++;
	}
}

// get the top of the queue, and remove it from the queue
public Node getAndRemoveTop(){
	if (this.top == null || this.length == 0) return null;
	else {
		Node t = this.top;
		if (this.length > 1){
			this.top = this.top.next;
		}
		else{// length == 1
			this.top = null;
			this.bottom = null;
		}
		t.next = null;
		this.length --;
		return t;
	}
}

}[/code]

#11

[code]/*

  • Shortest Path Between 2 given cities
  • using Floyd’s Algorithm

/
import java.io.;

/**

  • GOOGLE

*/
public class Main{

public Main() {
}

private static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
    // TODO code application logic here
    int S[][] = new int [6][6]; /* Creating the adjacency matrix, this is the last adjacency matrix */
           
            S[0][0] = 0;//Defining Values
            S[0][1] = 0;
            S[0][2] = 0;
            S[0][3] = 0;
            S[0][4] = 0;
            S[0][5] = 0;
           
            S[1][0] = 0;
            S[1][1] = 0;
            S[1][2] = 2;
            S[1][3] = 3;
            S[1][4] = 2;
            S[1][5] = 4;
           
            S[2][0] = 0;
            S[2][1] = 1;
            S[2][2] = 0;
            S[2][3] = 4;
            S[2][4] = 4;
            S[2][5] = 4;
           
            S[3][0] = 0;
            S[3][1] = 1;
            S[3][2] = 4;
            S[3][3] = 0;
            S[3][4] = 4;
            S[3][5] = 4;
           
            S[4][0] = 0;
            S[4][1] = 2;
            S[4][2] = 2;
            S[4][3] = 3;
            S[4][4] = 0;
            S[4][5] = 3;
           
            S[5][0] = 0;
            S[5][1] = 4;
            S[5][2] = 4;
            S[5][3] = 4;
            S[5][4] = 4;
            S[5][5] = 0;
           
 
           
    System.out.println("Escribe la ciudad de origen");/*Ask for the initial point, from 1 to 5 */


    int i = Integer.parseInt(in.readLine());
   
    System.out.println("Escribe la ciudad destino");/*Ask for the final point*/
    int j = Integer.parseInt(in.readLine());
   
    int l = j;
    int k=0;
    String ruta = "";
    String ruta0 = "";
   
    if (S[i][j] == j) /*If j = S[i][j] there is a direct conection between i and j */
        System.out.println("La ruta mas corta es ir de: " + i + " a " + j );
   
    else{ /* if theres no direct connection between i and j, S[][] has to be evaluated to find the shortest path. */

/*Here is the main problem… this how i programmed the last part of the *algorithm, but it is not
*correct.
*These Whiles has to check if S[i][l] is equal to l if so, there is a direct *connection between i
*and j, if not between i and j you have to pass through S[i][j], and *evaluate this point with
*the new value of l
*/
k = S[i][l];
while ( k != l){
ruta = S[i][l] + “” + ruta + “”;
l = S[i][l];

        }
       
        k = S[l][j];
         while ( k != l){
            ruta0 = S[l][j] + "" + ruta0 + "";
            l = S[l][j];
           
        }
        if(j<i)
        System.out.println("La ruta mas corta a tomar es la sigueinte: " + i + " " + ruta +

" " + ruta0 + " "+ j);
else
System.out.println("La ruta mas corta a tomar es la sigueinte: " + i + " " +

ruta0 + " " + ruta + " "+ j);

    }
   
   
   
   
}

}[/code]
>

#12

[quote=Marcio Duran][quote]
E na verdade o floyd teria que retornar o menor caminho entre 2 vertices que no caso seriam duas cidades
Se vc entra com uma cidade de origem e dentro ela seria por exemplo o vertice 1 e vc entraria com a segunda cidade que seria por exemplo o vertice 8
Ele teria que mostrar quais vertices que ele percorreu para chegar no vertice 8. Qual o menor caminho
[/quote]

[code]
// Now the shortest distance between i and j will be in dist[i][j]
int dist[N][N]; // For some N
int i, j, k;
// Input data into dist, where dist[i][j] is the distance from i to j.

for ( k = 0; k < N; k++ )
for ( i = 0; i < N; i++ )
for ( j = 0; j < N; j++ )
dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] );

[/code][/quote]

Onde eu tenho que declarar o N? E o que ele deve receber?

O método min tb não foi declarado, e como devo declarar o mesmo?

#13

Bom são algums exemplos acima e tem video também explicando matematicamente sobre Floyd, googleando ai tem muito material em Java.

#14

[quote=Designer]A minha pergunta agora é como saber se o algoritmo esta percorrendo o menor caminho ou não?
Tipo como eu devo chamar o método floyd na main?
De que forma eu devo fazer para imprimir o menor caminho?[/quote]

:arrow: Googleando por ai !!!

[code]// Floyd-Warshall algorithm
//

public class FloydWarshall {

// Debugging for internal use.
private static final boolean debug = false;

int numVertices; // Number of vertices (when initialized).

double[][] adjMatrix; // The adjacency matrix (given as input).

double[][] Dk, Dk_minus_one; // Matrices used in dynamic programming.

public void initialize (int numVertices)
{
this.numVertices = numVertices;

// Initialize Dk matrices.
Dk = new double [numVertices][];
Dk_minus_one = new double [numVertices][];
for (int i=0; i < numVertices; i++){
  Dk[i] = new double [numVertices];
  Dk_minus_one[i] = new double [numVertices];
}

}

public void allPairsShortestPaths (double[][] adjMatrix)
{
// Dk_minus_one = weights when k = -1
for (int i=0; i<numVertices; i++) {
for (int j=0; j><numVertices; j++) {
if (adjMatrix[i][j] > 0)
Dk_minus_one[i][j] = adjMatrix[i][j];
else
Dk_minus_one[i][j] = Double.MAX_VALUE;
// NOTE: we have set the value to infinity and will exploit
// this to avoid a comparison.
}
}

// Now iterate over k.

for (int k=0; k<numVertices; k++) {

  // Compute Dk[i][j], for each i,j

  for (int i=0; i><numVertices; i++) {
    for (int j=0; j><numVertices; j++) {
      if (i != j) {

        // D_k[i][j] = min ( D_k-1[i][j], D_k-1[i][k] + D_k-1[k][j].
        if (Dk_minus_one[i][j] >< Dk_minus_one[i][k] + Dk_minus_one[k][j])
          Dk[i][j] = Dk_minus_one[i][j];
        else 
          Dk[i][j] = Dk_minus_one[i][k] + Dk_minus_one[k][j];

      }
    }
  }

  // Now store current Dk into D_k-1
  for (int i=0; i<numVertices; i++) {
    for (int j=0; j><numVertices; j++) {
      Dk_minus_one[i][j] = Dk[i][j];
    }
  }

} // end-outermost-for


// Next, build the paths by doing this once for each source.

// ... (not shown) ...

}

//---------------- Test case -----------------------------------------------

public static void main (String[] argv)
{
// A test case.
double[][] adjMatrix = {
{0, 1, 7, 0, 5, 0, 1},
{1, 0, 1, 0, 0, 7, 0},
{7, 1, 0, 1, 7, 0, 0},
{0, 0, 1, 0, 1, 0, 0},
{5, 0, 7, 1, 0, 1, 0},
{0, 7, 0, 0, 1, 0, 1},
{1, 0, 0, 0, 0, 1, 0},
};

  int n = adjMatrix.length;
  FloydWarshall fwAlg = new FloydWarshall ();
  fwAlg.initialize (n);
  fwAlg.allPairsShortestPaths (adjMatrix);
  
  // Print paths ... (not shown) ...

}

}[/code]>

#15

Pessoal eu estou com muita dficuldade em imprimir o caminho percorrido de uma vertice a outro!

É possivel algum me dar uma ajuda pois grafo não aceitam ponteiros!!E se tornam mais dificil ainda. Já tentei de várias formas mas de nenhuma forma da certo!!!

#16