所以基本上我需要使用 goroutines 做一個 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
}
問題是這段代碼在其實際狀態下不能很好地使用 goroutines。我想知道我應該把它放在哪里才能使我的結果更快（因為這里就像沒有 goroutines）。在此先感謝任何可能給我一些解決方案的人。
uj5u.com熱心網友回復：
您的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通道中讀取并添加到地圖中。我個人更喜歡這個解決方案，因為它避免了同時修改地圖。接下來，遍歷節點，為每個節點啟動一個 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
}
uj5u.com熱心網友回復：
我認為將您的等待移到 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();
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/369720.html
下一篇：pythons在go中列舉