Алгоритм Флойда-Варшалла - кратчайший путь - сохранить индекс путей в массив

Question

Алгоритм Флойда-Варшалла - кратчайший путь - сохранить индекс путей в массив

Я реализую алгоритм Флойда-Варшалла для симметричного, неориентированного графа. На данный момент я рассчитал лучший путь для каждой точки подключения. Моя проблема заключается в том, что я хочу сохранить индексные точки, рассчитанные для накопленного веса, чтобы впоследствии можно было записывать названия точек из маршрута. Я хочу сохранить их в списке, но я не знаю, какие индексы следует записать в функцию addDrawPointsToList (int a, int b, int [] [] M). а и б - это точки, между которыми я хочу сохранить путевые точки

0 - тот же узел
1 - есть связь между узлами
Х - без связи = 999 вес

КОД:

public class FloydWarshallAlg {
static int[][] P;
static List<Integer> lista;
static final int N = 43;
static final int X = 999;

public static void main(String[] args) {

    int M[][] = new int[][]{
        {0, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {1, 0, 1, X, X, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, 1, 0, 1, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, 1, X, 0, X, 1, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, 1, 1, X, X, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, 1, X, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, 1, X, X, 0, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, 1, X, X, 1, 0, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, 1, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, X, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, X, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, X, X, 1, 1, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, X, X, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, X, X, X, 0, 1, X, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, X, X, X, 1, 0, 1, X, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, 1, 1, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X},
        {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0}};

    lista = new ArrayList<Integer>();
    System.out.println("Main Matrix.");
    printMatrix(M);
    System.out.println("Shortest Path Matrix.");
    printMatrix(FloydAlgo(M));
    addDrawPointsToList(3, 12);
    printList(lista);
}

public static List addDrawPointsToList(int a, int b, int[][] M) {

    return lista;
}

public static int[][] FloydAlgo(int[][] M) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                // to keep track.;
                if (M[j][i] + M[i][k] < M[j][k]) {
                    M[j][k] = M[j][i] + M[i][k];
                }
            }
        }
    }
    return M;
}

public static void printMatrix(int[][] Matrix) {
    System.out.print("\n\t");
    for (int j = 0; j < N; j++) {
        System.out.print(j + "\t");
    }
    System.out.println();
    for (int j = 0; j < 347; j++) {
        System.out.print("-");
    }
    System.out.println();
    for (int i = 0; i < N; i++) {
        System.out.print(i + " |\t");
        for (int j = 0; j < N; j++) {
            if (Matrix[i][j] == 999) {
                System.out.print("X");
            } else {
                System.out.print(Matrix[i][j]);
            }
            System.out.print("\t");
        }
        System.out.println("");
    }
    System.out.println("\n");
}

public static void printIntArray(int A[]) {
    for (int i = 0; i < N; i++) {
        System.out.print(A[i] + " ");
    }
}

public static void printList(List L) {
    for (int i = 0; i < L.size(); i++) {
        System.out.print(L.get(i) + ", ");
    }
    System.out.println("\nList size: " + L.size());
}}

Я чувствую, что это может быть небольшая проблема, которую нужно решить, но я начинающий программист, и я не вижу решения. Буду благодарен за любые советы. Извините за мой английский;<

-3

java algorithm graph-algorithm shortest-path floyd-warshall

Источник

user6394062 30 дек '16 в 17:09

1 ответ

Другие вопросы по тегам java algorithm graph-algorithm shortest-path floyd-warshall

user1126268 30 дек '16 в 21:34 2016-12-30 21:34 · Answer 1 · 2016-12-30 21:34

Я не знаю что addDrawPointsToList должен делать, но в целом, если вы хотите получить путь от Флойд-Варшалла, вы должны иметь в виду, что вы вычисляете на i-th шаг.

Если M[j][i] + M[i][k] < M[j][k]кратчайший путь от j в k используя узлы 1, ..., i проходит через i, Следовательно, кратчайший путь можно разложить по кратчайшему пути из j в i и кратчайший путь от j в k, Позволять A[j][k] быть этим посредническим узлом.

if (M[j][i] + M[i][k] < M[j][k]) {
    A[j][k] = i;
    M[j][k] = M[j][i] + M[i][k];
}

Затем, чтобы получить путь от i в k:

get_path(s, t) {
    if A[s][t] = s or A[s][t] = t then return [s]
    // + is here the concatenation
    return get_path(s, A[s][t]) + get_path(A[s][t], t)
}

Это основная идея, теперь вы можете написать код Java для симуляции этого.