In the journey to the source of food, each ant will leave behind a pheromone trail. An ant which leaves from a vertex is more likely to choose the path with the highest concentration of pheromone to continue his journey. Although, some ants won't choose the path with the highest pheromone concentration. This encourages exploration of the area. If there exist a shorter path, eventually some ant will find it. The probability for an ant to move from some node i to another node j is obtained:
In this equation, τ is the pheromone variable and η a heuristic variable. The heuristic variable represents a short term quality measure, in this case the distance between two vertices. The relative importance between the pheromone and heuristic variables are set by α and β.
In the above equation, the first term is the residual pheromone level after evaporation. The last term is the pheromone level added by the ants who have just walked over route ij.