如何在 iOS/Swift 中使用 Dijkstra 算法找到多个可能的路径

Question

我正在使用 Dijkstra 算法寻找两个节点之间的路径。

我已经成功地建立了两个节点之间的最短路径，但现在我想要两个节点之间的所有可能路径来完成某些特定任务。

我正在使用 Dijkstra's algorithm for now。我该怎么做？

Answer 1

此 class 将为您提供两个节点之间的所有可能路径。只需从此处复制此 class，在底部我将提供如何使用此算法。

class Graph {

private var v : Int
private var adjList : [[Int]] = []
private var allPossiblePath : [[Int]] = []
init(vertices : Int)
{
    v = vertices
    initAdjList()
}
private func initAdjList()
{
    adjList = [[Int]](repeating: [0], count: v)
    for i in 0..<v
    {
        adjList[i] = []
    }
}

public func addEdge(u : Int,v : Int)
{
    adjList[u].append(v)
}

public func printAllPaths(s : Int,d : Int)
{
    var isVisited = [Bool](repeating: (0 != 0),count: v)
    var pathList = [Int]()
    pathList.append(s)
    printAllPathsUtil(u: s, d: d, isVisited:&isVisited, localPathList:&pathList)
}

private func printAllPathsUtil(u: Int, d: Int, isVisited: inout [Bool], localPathList: inout [Int])
{
    if u == d
    {
        if (localPathList.count < 55)
        {
            allPossiblePath.append(localPathList)
            //print(localPathList)
        }
        return
    }
    isVisited[u] = true
    for i in adjList[u]
    {
        if !isVisited[i]
        {
            localPathList.append(i)
            //print(i)
            printAllPathsUtil(u: i, d: d, isVisited:&isVisited, localPathList:&localPathList)
            localPathList.removeAll{[=10=] == i}
        }
    }
    isVisited[u] = false
}
public func getAllPossiblePath() -> [[Int]]
{
    return allPossiblePath
}}

这是使用方法的代码。

 let g = Graph(vertices: data_Rout.count)
    
  for routData in data_Rout
  {
      g.addEdge(u: routData.route_source_id, v: routData.route_destination_id)
  }
 g.printAllPaths(s: fetchSingleMyNodeFromList(station_code: "\(routsAndFilterDepartStation!.station_code)")!.station_id,d: fetchSingleMyNodeFromList(station_code: "\(routsAndFilterDestinationStation!.station_code)")!.station_id)
 let allPossiblePaths = g.getAllPossiblePath()

如何在 iOS/Swift 中使用 Dijkstra 算法找到多个可能的路径

How to find multiple possible path using Dijkstra's algorithm in iOS/Swift

ios

swift

shortest-path

dijkstra