ścieżka z algorytmu FordaBellmana

Odpowiedz Nowy wątek
2009-04-19 20:24
0

Witam

mam nastepujacy problem.

public static int[] tablica(int[][] macsas, int n, int od) {

    int[][] A = macsas;
    int[] D = new int[n];
    int i,j,k;
    int N;

    for (i=0;i<n;i++) D[i]=A[od-1][i];
    for (k=0;k<=n-2;k++) {
        for (i=0;i<n;i++)
            for (j=0;j<n;j++) {
                if (D[j]+A[j][i]>nieskonczonosc)
                    N=nieskonczonosc; 
                else
                    N=D[j]+A[j][i];
                D[i]=Math.min(D[i],N);
            }
    }
    return D;
}

gdzie
macsas - macierz sasedztwa
n - liczba wierzcholkow
od - wierzcholek od ktorego liczone sa wagi;

Chodzi mi o to, ze wagi dla wszystkich krawedzi mam 1 (poniewaz nie sa mi one potrzebne do niczego, a algorytm ich wymagal) i powyzszy algorytm wylicza mi wszystkie odleglosci od danego wierzcholka (suma wag). Czy jest mozliwe na podstawie tych danych albo tego algorytmu stworzyc tablice z konkretna sciezka od - do? Gdyby wagi sie roznily to nie mialbym problemu, a tak siedze nam tym pol dnia i nie moge nic wymyslic sensownego ;/

z gory dziekuje za pomoc

pozdrawiam
Antek

Pozostało 580 znaków

2009-04-26 21:52
0

proponuje wymienić FB na zwykłego BFS-a skoro wagi mają wartość 1.W ten sposób dostaniesz liniówke zamiast O(n*n).Ze znajdowaniem ścieżki to już pikuś,w necie masz pewnie sporo artykułów na temat BFS-a itp.


Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0