Golang Dijkstra 协程

Question

所以基本上我需要使用 goroutines 做一个 Dijkstra 程序。

除了 goroutines 有点问题外，我基本上什么都做了。由于它是 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
}

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

Answer 1

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

Answer 2

您的 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，它将从 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
}

Golang Dijkstra 协程

Golang Dijkstra goroutines

parallel-processing

dijkstra

go

goroutine