Задача состояит из двух пунктов:
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);