我如何在不包含O（n）^ 3的情况下遍历包含2D数组的对象？

Question

希望这不是一个问题的具体问题，但我希望能深入了解如何使用嵌套的对象和数组，而无需编写运行O（n）^ 2或O（n）^ 3的程序。] >

以下是我构建的程序，用于查找从A点到B点的最便宜航班，如果航班价格相同，则航班数量最少。您会看到我在哪里标记效率不高的零件。我怎样才能使这些效率更高？

//returns an object with an array of IDs that will get you to a destination at the lowest cost. if same cost, then the least amount of flights flights

function leastExpensiveFlight(flightInfo, start, end) {
  var numOfTimes = 1
  var combinedValues = []
  var minValue
  var indexOfMinValue;
  var numOfFlights = []
  var minNumberOfFlights;
  var startTimes = flightInfo.reduce((startTimes, f, index) => {
    if (f[0] == start) {
      startTimes[numOfTimes] = [f];
      numOfTimes++
    }
    return startTimes
  }, {})
  //below is O(n)^2  
  //Gets the Flights where Location 1 = start 
  for (i = 0; i < Object.keys(startTimes).length; i++) {
    for (j = 0; j < startTimes[Object.keys(startTimes)[i]].length; j++) {
      flightInfo.forEach((f, ) => {
        if (startTimes[Object.keys(startTimes)[i]][j] &&
          f[0] === startTimes[Object.keys(startTimes)[i]][j][1] &&
          startTimes[Object.keys(startTimes)[i]][j][1] <= end &&
          f[1] <= end) {
          if (!startTimes[Object.keys(startTimes)[i]].includes(f)) {
            startTimes[Object.keys(startTimes)[i]].push(f)
          }
        }
      })
    }
  }
  //below is O(n)^3!!
  //Finds trips that will get to the destination
  Object.keys(startTimes).forEach((flights) => {
    startTimes[flights].forEach((subFlights1, sFIndex1) => {
      startTimes[flights].forEach((subFlights2, sFIndex2) => {
        if (subFlights1[0] === subFlights2[0] &&
          subFlights1[1] === subFlights2[1] &&
          sFIndex1 != sFIndex2) {
          if (subFlights1[2] >= subFlights2[2]) {
            startTimes[flights].splice(sFIndex1, 1)
          } else {
            startTimes[flights].splice(sFIndex2, 1)
          }
        }
      })
    })
  })
  //below is O(n)^2  
  //Finds the trip with the minimum value and, if same price, least amount of flights
  Object.keys(startTimes).forEach((flights, sTIndex) => {
    startTimes[flights].forEach((subFlights, sFIndex) => {
      if (sFIndex == 0) {
        combinedValues[sTIndex] = subFlights[2]
        numOfFlights.push(1)
      } else {
        combinedValues[sTIndex] += subFlights[2]
        numOfFlights[sTIndex] += 1
      }
      if (sFIndex === startTimes[flights].length - 1 &&
        ((combinedValues[sTIndex] <= minValue) ||
          !minValue)) {
        if ((!minNumberOfFlights ||
            minNumberOfFlights > numOfFlights[sTIndex])) {
          minNumberOfFlights = numOfFlights[sTIndex]
        }
        if (combinedValues[sTIndex] === minValue &&
          numOfFlights[sTIndex] === minNumberOfFlights ||
          (combinedValues[sTIndex] < minValue &&
            numOfFlights[sTIndex] >= minNumberOfFlights) ||
          !minValue) {
          minValue = combinedValues[sTIndex];
          indexOfMinValue = sTIndex
        }
      }
    })
  })

  return startTimes[Object.keys(startTimes)[indexOfMinValue]]
} //Big O is O(n)^3

//2D Array: data[0][0] = Location start,
//          data[0][1] = Location end,
//          data[0][2] = Price,
//          
var data = [
  [4, 5, 400],
  [1, 2, 500],
  [2, 3, 300],
  [1, 3, 900],
  [2, 3, 100],
  [3, 4, 400]
]

//so from location 1 - location 3, the cheapest route would be: [1,2,500],[2,3,100]
console.log(JSON.stringify(leastExpensiveFlight(data, 1, 3)));

非常感谢您的帮助。我正在努力提高编码水平，因此可以进入我的工程部门，但是正如您所看到的，我还有很长的路要走。

[[EDIT]-抱歉，我刚才在其中有一个错误的陈述。

希望这不是一个具体的问题，但我希望能深入了解如何使用嵌套的对象和数组，而无需编写运行O（n）^ 2或O（n）^ 3的程序。下面是一个程序...

Answer 1

我首先通过为起点和终点之间的每个可能路径构造一个graph来解决这个问题。提供给定起始节点和已访问节点列表的功能，可以浏览数据以查找从该节点引出的每个路径。对于尚未访问not