最短路径数组

Question

给出数组

[[“ 5”，“ A”，“ B”，“ C”，“ D”，“ F”，“ A-B”，“ A-C”，“ B-C”，“ C-D”，“ D-F”];

在这里我要对数组进行剪切的位置是5，在这种情况下，它会得到-

[[“ A-B”，“ A-C”，“ B-C”，“ C-D”，“ D-F”]

我需要找到A和F之间的最短路径

[[“ A-B”，“ A-C”，“ B-C”，“ C-D”，“ D-F”]

正确的输出为：A-C-D-F

任何解决此算法的JavaScript函数？

const findShort = (arrayStrings) => {
    let index = arrayStrings.shift();
    arrayStrings.splice(0, index)
    let allChars = arrayStrings.join('-').split('-')
    let lastItem = ''
    let shortPath = []
    allChars.map(item => {
        if (item > lastItem) {
            shortPath.push(item)
        }
        lastItem = item;
    })
    shortPath = [...new Set(shortPath)].join('-')
    return shortPath; // returns "A-B-C-D-F" and should return A-C-D-F
}


let test = ["5", "A", "B", "C", "D", "F", "A-B", "A-C", "B-C", "C-D", "D-F"];

findShort(test)

Answer 1

[不确定通过数组中的cut表示什么。我假设它是在数组中的索引5之后，您具有一些可以在其中搜索最短路径的信息，它们是如您所示的边：

["A-B", "A-C", "B-C", "C-D", "D-F"]，当可视化时将看起来像：

在那种情况下，您可以构建可以由Adjacency List表示的图形，并且可以使用该列表实现Breadth First Search以获取从起始顶点到目标顶点的最短路径。