Na podstawie artykułu na wikipedii udało mi się stworzyć sam algorytm, tworzy się poprawna tabela optymalnych kosztów. Jednak mam problem z odczytaniem samej najkrótszej ścieżki. Czytałem, że trzeba zrobić drugą tablicę, w której się właśnie zapisuję wierzchołki przechodnie, jednak utknąłem i nie mogę sobie dalej poradzić.
public class FloydWarshall
{
double tablica[][];
double sciezka[][];
double wierzcholki;
/*
* Ten fragment pobiera tablicę z klasy Ramka.java
*/
public FloydWarshall(double wierzcholki)
{
tablica = new double[(int) (wierzcholki+1)][(int) (wierzcholki+1)];
sciezka= new double[(int) (wierzcholki+1)][(int) (wierzcholki+1)];
this.wierzcholki = wierzcholki;
}
/*
* Algorithm Floyda-Warshalla
*/
public double[][] floydwarshall(double tablica1[][])
{
for (int i = 1; i <= wierzcholki; i++)
{
for (int j = 1; j <= wierzcholki; j++)
{
tablica[i][j] = tablica1[i][j];
sciezka[i][j] = j;
}
}
for (int w = 1; w <= wierzcholki; w++)
{
for (int i = 1; i <= wierzcholki; i++)
{
for (int j = 1; j <= wierzcholki; j++)
{
if (tablica[i][w]
+ tablica[w][j] < tablica[i][j])
tablica[i][j] = tablica[i][w]
+ tablica[w][j];
sciezka[i][j]=w;
}
}
}
Path(wierzcholki,wierzcholki);
return tablica;
}
public static void main(String... arg)
{
}
List<Double> Path(double i, double j) {
if (sciezka[(int) i][(int) j] == Double.POSITIVE_INFINITY) {
return null;
}
List<Double> Wynik = new ArrayList<Double>();
while (i != j) {
i = sciezka[(int) i][(int) j];
Wynik.add(i);
}
return Wynik;
}
}
Potem jeszcze próbowałem coś wykombinować z tym kodem http://stackoverflow.com/questions/10638750/how-to-list-down-vertices-passed-in-floyd-warshall-algorithm?rq=1 ale program mi się zapętla :)