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){&nbsp; &nbsp;defer wg.Done()&nbsp; &nbsp;//your calculations&nbsp; &nbsp;// ...&nbsp; &nbsp;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) {&nbsp; &nbsp; var wg sync.WaitGroup&nbsp;&nbsp; &nbsp; datach := make(chan data)&nbsp; &nbsp; done := make(chan bool)&nbsp; &nbsp; dijk := make(map[int]map[int][]int)&nbsp; &nbsp; distance := make(map[int]map[int]int)&nbsp; &nbsp; neighbors := getAllNeighbors(list, nodes)&nbsp; &nbsp; //start a goroutine that will read from the data channel&nbsp; &nbsp; go func(){&nbsp; &nbsp; &nbsp; for d := range dataCh {&nbsp; &nbsp; &nbsp; &nbsp; dijk[d.node] = d.routes&nbsp; &nbsp; &nbsp; &nbsp; distance[d.node] = d.distances&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; done <- true //this is used to wait until all data has been read from the channel&nbsp; &nbsp; }()&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; wg.Add(len(nodes))&nbsp; &nbsp; for _, node := range nodes {&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; go oneDijkstra(node, &wg, list, nodes, neighbors, dataCh)&nbsp; &nbsp; }&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; wg.Wait()&nbsp; &nbsp; close(dataCh) //this closes the dataCh channel, which will make the for-range loop exit once all the data has been read&nbsp; &nbsp; <- done //we wait for all of the data to get read and put into maps&nbsp; &nbsp; 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&nbsp; &nbsp; &nbsp; &nbsp; wg.Add(1)&nbsp; &nbsp;//We add our next goroutine in the waitgroup&nbsp; &nbsp; &nbsp; &nbsp; go func() { //goroutine&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;defer wg.Done();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;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&nbsp; &nbsp; &nbsp; &nbsp; }()&nbsp; &nbsp; }&nbsp; &nbsp; wg.wait();