The task consists of two points:
1. Implement the function floyd, which takes one paths argument as input - an array of graph edges with their cost. Count count as bidirectional (i.e. if the path is from from to to, then from to to from), too. The function should display a string on the console, which is a matrix of distances between the vertices of the graph.
With this I figured out the matrix is displayed. The code below can be run.
2. The function should output to the console a set of lines, each of which displays the most optimal path from vertex 1 to all vertices, then the most optimal path from vertex 2 to all vertices except 1, etc. If there is no path from a vertex to a vertex, output "no way" instead of the path.
For this, I started a two-dimensional array arrHistory, in which I first store the last vertex to which I go. Now I need to find intermediate peaks, which we will enter when searching for the optimal path.
I try to do it where we compare the prices of the ribs and look for the best, but this is clearly the wrong decision. As a matter of fact, I cannot understand how I can write intermediate peaks into the arrHistory array.
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); 
