1

Задача состояит из двух пунктов:

1. Реализуйте функцию floyd, принимающую на вход один аргумент paths - массив ребер графа с их стоимостью. Граф считать двунаправленным (т.е. если путь есть из from в to, то из to в from) тоже есть. Функция должна выводить на консоль строку, которая представляет собой матрицу расстояний между вершинами графа.

С этим я разобралась, матрица выводится. Код ниже можно запустить.

2. Функция должна выводить на консоль набор строк, каждая из которых отображает самый оптимальный путь из вершины 1 во все вершины, далее самый оптимальный путь из вершины 2 во все вершины кроме 1 и т.д. Если пути из вершины в вершину нет - выводить "no way" вместо пути.

Для этого я завела двумерный массив arrHistory, в котором сначала храню последнюю вершину, в которую иду. Теперь мне нужно найти промежуточные вершины, в которые мы будем заходить при поиске оптимального пути.

Я пытаюсь это сделать там где мы сравниваем цены ребер и ищем оптимальные, но это явно неправильное решение. По сути я не могу понять как мне записать в массив arrHistory промежуточные вершины.

    var flag = true;
    while(flag) {
        flag = false;
        for (var i = 1; i < arrPrices.length; i++) {
        for (var j = 1; j < arrPrices.length; j++) {
            for (var k = 1; k < arrPrices.length; k++) {
                if (arrPrices[i][j] > arrPrices[k][i] + arrPrices[k][j]) {
                    arrPrices[i][j] = arrPrices[k][i] + arrPrices[k][j];
                    //надо запомнить следующую вершину, в которую я иду, но такой вариант не верен
                    arrHistory[i][j] = arrPrices[k];
                    flag = true;
                }
            }
        }
    }
}

function floyd(edjes) {
    var arrPrices = [];
    for (var jj = 0; jj < edjes.length; jj++) {
        var item = edjes[jj];
        arrPrices[item.from] = arrPrices[item.from] || [];
        arrPrices[item.to] = arrPrices[item.to] || [];
        arrPrices[item.from][item.to] = item.price;
        arrPrices[item.to][item.from] = item.price;
    }
    //Создаю матрицу истории
    var arrHistory = [];
    for (var c = 0; c < edjes.length; c++) {
        var item2 = edjes[c];
        arrHistory[item2.from] = arrHistory[item2.from] || [];
        arrHistory[item2.to] = arrHistory[item2.to] || [];
        arrHistory[item2.from][item2.to] = item2.to;
        arrHistory[item2.to][item2.from] = item2.from;
    }
    for (var l = 1; l < arrPrices.length; l++) {
        arrPrices[l] = arrPrices[l] || [];
        arrPrices[l].length = arrPrices.length;
        for (var d = 1; d < arrPrices[l].length; d++) {
            if (typeof arrPrices[l][d] === 'undefined') {
                arrPrices[l][d] = Infinity;
            }
        }
    }
    for (var z = 1; z < arrHistory.length; z++) {
        arrHistory[z] = arrHistory[z] || [];
        arrHistory[z].length = arrHistory.length;
        for (var x = 1; x < arrHistory[z].length; x++) {
            if (typeof arrHistory[z][x] === 'undefined') {
                arrHistory[z][x] = 0;
            }
        }
    }
    var flag = true;
    while(flag) {
        flag = false;
        for (var i = 1; i < arrPrices.length; i++) {
            for (var j = 1; j < arrPrices.length; j++) {
                for (var k = 1; k < arrPrices.length; k++) {
                    if (arrPrices[i][j] > arrPrices[k][i] + arrPrices[k][j]) {
                        arrPrices[i][j] = arrPrices[k][i] + arrPrices[k][j];
                        //надо запомнить следующую вершину, в которую я иду, но такой вариант не верен
                        arrHistory[i][j] = arrPrices[k];
                        flag = true;
                    }
                }
            }
        }
    }

    var str = "";
    for (var i = 1; i < arrPrices.length; i++) {
        for (var j = 1; j < arrPrices[i].length; j++) {
            str += arrPrices[i][j] === Infinity ? '_' : arrPrices[i][j];
            str += ' ';
        }
        str += '\n'
    }
    alert(str)
}

var graph = [
    { from: 1, to: 2, price: 7},
    { from: 1, to: 3, price: 9},
    { from: 6, to: 1, price: 14},
    { from: 2, to: 3, price: 10},
    { from: 4, to: 2, price: 15},
    { from: 4, to: 3, price: 11},
    { from: 5, to: 4, price: 6},
    { from: 5, to: 6, price: 8},
    { from: 6, to: 3, price: 2}
];
floyd(graph);

1 ответ 1

1

Это не ответ, но в комментарии вся разметка полетит.

for (var i = 1; i < arrPrices.length; i++) {
    for (var j = 1; j < arrPrices.length; j++) {
        for (var k = 1; k < arrPrices.length; k++) {
            if (arrPrices[i][j] > arrPrices[k][i] + arrPrices[k][j]) {

Где вы такой алгоритм флойда нашли? Основная идея что мы заменяем путь (порядок переменных внимательно!) из j в k на 2 пути из j в i и i в k.

Т.е. уже правильнее

for (var i = 1; i < arrPrices.length; i++) {
        for (var j = 1; j < arrPrices.length; j++) {
            for (var k = 1; k < arrPrices.length; k++) {
                if (arrPrices[j][k] > arrPrices[j][i] + arrPrices[i][k]) {
                    arrPrices[j][k] > arrPrices[j][i] + arrPrices[i][k];

                    arrHistory[j][k] = i;
                    flag = true;
                }
            }

Теперь как восстановить ответ, пишу только идею.

Мы пытаемся восстановить ответ между A и B в массиве arrHistory[j][k] есть C. Оно будет использовано в пути, т.е. A --- --->C --- --->B Дальше рекурсивно аналогично.

http://e-maxx.ru/algo/floyd_warshall_algorithm рекомендую.

0

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.