Golang Dijkstra 协程

Question

所以基本上我需要使用 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        }    }}问题是这段代码在其实际状态下并不能很好地使用 goroutines。我想知道我应该把它放在哪里以使我的结果更快（因为这里就像没有 goroutines）。提前感谢任何能够给我一些解决方案的人。

Answer 1

您的函数未同时处理节点的主要原因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函数中，您需要更改一些内容。

dataCh首先，启动一个从通道读取并添加到地图的 goroutine 。我个人更喜欢这种解决方案，因为它可以避免同时修改地图。接下来，遍历节点，为每个节点启动一个 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

}

Answer 2

我认为将您的等待移到 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();