如何计算此Q＆A流程的最短和最长路径？

Question

我有问答&像下面这样的流程：

的基本思路是，根据选择的问题的答案，不同的问题会接着问。

我目前代表这个问答&与以下JavaScript对象的流程：

var QAndAObj = { 
    1: { 
    question: 'Question 1', 
    answers: [ 
     { 
     answerText: 'Answer 1-1', 
     nextQuestion: 2 
     }, 
     { 
     answerText: 'Answer 1-2', 
     nextQuestion: 3 
     } 
    ] 
    }, 
    2: { 
    question: 'Question 2', 
    answers: [ 
     { 
     answerText: 'Answer 2-1', 
     nextQuestion: 3 
     }, 
     { 
     answerText: 'Answer 2-2', 
     nextQuestion: null 
     } 
    ] 
    }, 
    3: { 
    question: 'Question 3', 
    answers: [ 
     { 
     answerText: 'Answer 3-1', 
     nextQuestion: 4 
     }, 
     { 
     answerText: 'Answer 3-2', 
     nextQuestion: null 
     }, 
     { 
     answerText: 'Answer 3-3', 
     nextQuestion: null 
     } 
    ] 
    }, 
    4: { 
    question: 'Question 4', 
    answers: [ 
     { 
     answerText: 'Answer 4-1', 
     nextQuestion: null 
     }, 
     { 
     answerText: 'Answer 4-2', 
     nextQuestion: null 
     } 
    ] 
    } 
}; 

向用户显示一个进度条，我希望能够通过计算最长和最短路径问题流程。

我最初的想法是写一个递归函数像下面走下来每一个可能的路径在流动：

function recurse(node) { 
    for (var i = 0; i < node.answers.length; i++) { 
    if (node.answers[i].nextQuestion) { 
     recurse(QAndAObj[node.answers[i].nextQuestion]); 
    } 
    } 
} 

上述功能确实让我打在流程中的每个节点，但我我不知道如何计算通过流量的最长和最短路径。

任何帮助/建议/代码将不胜感激。
非常感谢。

Answer 1

看一看这个jsFiddle的工作示例。

function shortAndLong(QATree, startNode) { 
    var paths = []; 
    function findAllPaths(startNode, currentCost) { 
     for (var i = 0; i < startNode.answers.length; i++) { 
      var child = startNode.answers[i]; 
      if (child.nextQuestion == null) { 
       paths.push(currentCost); 
      }else { 
       findAllPaths(QATree[child.nextQuestion], currentCost+1); 
      } 
     } 
    } 
    findAllPaths(startNode, 1); 
    return [Math.min.apply(Math, paths), Math.max.apply(Math, paths)] 
} 
console.debug('ans',shortAndLong(QAndAObj, QAndAObj[1]));//returns [2, 4] 
console.debug('ans',shortAndLong(QAndAObj, QAndAObj[2]));//returns [1, 3] 
console.debug('ans',shortAndLong(QAndAObj, QAndAObj[3]));//returns [1, 2] 
console.debug('ans',shortAndLong(QAndAObj, QAndAObj[4]));//returns [1, 1] 

的基础是

1. 创建通过图中的所有路径的列表，保持查找最多需要答案的数目
2. 和MIN