Самый длинный путь во взвешенном неориентированном графе

Question

Самый длинный путь во взвешенном неориентированном графе

function convertToRoman(num) {
  var romNumerals = [["M", 1000], ["CM", 900], ["D", 500], ["CD", 400], ["C", 100], ["XC", 90], ["L", 50], ["XL", 40], ["X", 10], ["IX", 9], ["V", 5], ["IV", 4], ["I", 1]];
  var runningTotal = 0;
  var roman = "";
  for (var i = 0; i < romNumerals.length; i++) {
    while (runningTotal + romNumerals[i][1] <= num) {
      runningTotal += romNumerals[i][1];
      roman += romNumerals[i][0];
    }
  }

 return roman;
}

0

algorithm graph graph-algorithm

задан DmitriBodiu 4 March 2019 в 07:36

1 ответ

Другие вопросы по тегам:

algorithm graph graph-algorithm

Похожие вопросы:

score 0 · Answer 1

Найти самый длинный путь в графе - задача NP-Complete. Вопреки распространенному мнению, это не означает, что это не может быть решено за полиномиальное время (на самом деле это одна из самых больших нерешенных проблем в информатике P против NP ). Тем не менее, это означает, что это по крайней мере так же сложно, как самые сложные проблемы в NP. Другими словами, может быть эффективный алгоритм для решения этой проблемы, но пока никто не смог его найти. По сути, это невозможно решить эффективно. Знание того, что каждый узел имеет преимущество перед каждым другим узлом, не меняет того факта, что эта проблема является NP-полной.