So basically I need to do a Dijkstra program using goroutines.

I've done basically everything except I have a little problem with the goroutines. Since it's a Dijkstra algorithm, I'm using a function to find the shortest path from a given node to all the others. The goroutine must help me to find the shortest path from n to n nodes as you can see in the code below.

//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
}

The problem is that this code in its actual state doesn't use well the goroutines. I would like to know where should I put it to make my results much faster(since here it's like there are no goroutines). Thank you in advance to any one who may be able to give me some solutions.

CodePudding user response：

The main reason why your Dijkstra function is not processing nodes concurrently is because you wait for the goroutine to finish within the loop (with wg.Wait()). Essentially, each node is not concurrently processed.

One potential solution:

First, modify your oneDijkstra function to receive a channel to which you would send the data (data is just your struct that contains all of the info).

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}
}

Next, in the Dijkstra function, you will need to change a couple of things.

First, start a goroutine that will read from the dataCh channel and add to the maps. I personally prefer this solution since it avoids maps being modified concurrently. Next, go through the nodes, start a goroutine for each and wait for everything to finish after the loop.

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
}

CodePudding user response：

I think moving your wait to after the for loop and assigning the results directly to your slices will do what you want.

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();