Golang Dijkstra goroutine

你在学习Golang相关的知识吗？本文《Golang Dijkstra goroutine》，主要介绍的内容就涉及到，如果你想提升自己的开发能力，就不要错过这篇文章，大家要知道编程理论基础和实战操作都是不可或缺的哦！

所以基本上我需要使用 goroutine 来做一个 dijkstra 程序。

除了 goroutine 有点问题之外，我基本上已经完成了所有操作。由于它是 dijkstra 算法，因此我使用一个函数来查找从给定节点到所有其他节点的最短路径。 goroutine 必须帮助我找到从 n 到 n 个节点的最短路径，如下面的代码所示。

//This function will get us all the shortest paths from all the nodes to all the other nodes
//list []Edge here is our list containing all the characteristics given by the .txt file
//nodes []int gives us all the nodes in our graph
//map[int]map[int][]int is all the results for the paths for e.g {1:{2:[1 2](the paths that it took) 3:[1 3]...} 2:{1:{2 1}...}...}
//map[int]map[int]int is all the distances for the different paths for e.g {1:{2:1 3:2 4:3...},2...}
func Dijkstra(list []Edge, nodes []int) (map[int]map[int][]int, map[int]map[int]int) {
    var wg sync.WaitGroup // Waitgroup so that we won't get some things done before all the goroutines are done
    dijk := make(map[int]map[int][]int)
    distance := make(map[int]map[int]int)
    //start := time.Now()
    neighbors := getAllNeighbors(list, nodes)
    //fmt.Print(neighbors)
    //We get all the neighbors for every node we have in our graph
    //{1:[{1 2 1},{1 3 2}],B:...}
    for _, node := range nodes { //for every node we have we are going to get the shortest path to all the other nodes
        var routes map[int][]int
        var distances map[int]int

        wg.Add(1)   //We add our next goroutine in the waitgroup
        go func() { //goroutine
            routes, distances = oneDijkstra(node, &wg, list, nodes, neighbors) //function that will give us the shortes path from the node to other nodes of the list
        }()
        wg.Wait() //We wait until the waitgroup is empty to do the rest of the code
        //We can't add routes to our dijk if it's not completed
        dijk[node] = routes
        //for this node, we add the other nodes with the way to take to have the shortest path with them
        distance[node] = distances
        //for this node, we add for every other node the cost it takes for the shortest path
    }
    //fmt.Print(time.Since(start))
    return dijk, distance
}

问题是这段代码在实际状态下并没有很好地使用 goroutine。我想知道我应该把它放在哪里才能使我的结果更快（因为这里好像没有 goroutine）。预先感谢任何能够给我一些解决方案的人。

正确答案

dijkstra 函数未同时处理节点的主要原因是因为您等待 goroutine 在循环内完成（使用 wg.wait()）。本质上，每个节点并不是同时处理的。

一个潜在的解决方案：

首先，修改您的 onedijkstra 函数以接收您要将数据发送到的通道（数据只是包含所有信息的结构）。

func ondedijkstra(node int, wg *sync.waitgroup, list []edge, nodes []int, neighbours []edge, datach chan<- data){
   defer wg.done()
   //your calculations
   // ...
   datach <- data{node, routes, distances}
}

接下来，在 dijkstra 函数中，您需要更改一些内容。

首先，启动一个 goroutine，该 goroutine 将从 datach 通道读取数据并添加到映射中。我个人更喜欢这个解决方案，因为它避免了 maps being modified concurrently。 接下来，遍历节点，为每个节点启动一个 goroutine，并等待循环后一切完成。

func dijkstra(list []edge, nodes []int) (map[int]map[int][]int, map[int]map[int]int) {
    var wg sync.waitgroup 
    datach := make(chan data)
    done := make(chan bool)
    dijk := make(map[int]map[int][]int)
    distance := make(map[int]map[int]int)
    neighbors := getallneighbors(list, nodes)

    //start a goroutine that will read from the data channel
    go func(){
      for d := range datach {
        dijk[d.node] = d.routes
        distance[d.node] = d.distances
      }
      done <- true //this is used to wait until all data has been read from the channel
    }()
    
    wg.add(len(nodes))
    for _, node := range nodes {  
        go onedijkstra(node, &wg, list, nodes, neighbors, datach)
    }
    
    wg.wait()
    close(datach) //this closes the datach channel, which will make the for-range loop exit once all the data has been read
    <- done //we wait for all of the data to get read and put into maps

    return dijk, distance
}

我认为将等待移至 for 循环之后并将结果直接分配给切片将满足您的要求。

for _, node := range nodes { //for every node we have we are going to get the shortest path to all the other nodes
        wg.Add(1)   //We add our next goroutine in the waitgroup
        go func() { //goroutine
           defer wg.Done();
           dijk[node] , distance[node] = oneDijkstra(node, &wg, list, nodes, neighbors) //function that will give us the shortes path from the node to other nodes of the list
        }()
    }
    wg.wait();

今天关于《Golang Dijkstra goroutine》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！