I think I have got a good solution together now. The A* solution is written as a feature issue and will be tested later on. First of all, here are some measurements I made with release mode: ( before changes where made) United Kingdom: Calculating path cost : 3.12 ms Calls to Add_edge : 10.50 ms Dijkstra_shortest_Path : 8.10 ms Retrieve data from list : 0.22 ms Total : 21.94 ms knowing that the add_edge was the biggest problem, the only solution I could see was to simplify the graph and reduce edges. Any vertexes with constant weight are now simulated. The simulation now is not 100% accurate, but the results speak for themselves: United Kingdom: Calculating path cost : 3.27 ms Calls to Add_edge : 4.28 ms Dijkstra_shortest_Path : 3.17 ms Retrieve data from list : 0.21 ms Total : 10.94 ms It is playable now, but there will be some bottlenecks later on in the game, as countries ally and we get larger graphs for each country. I have tried changing the list from vecS to ListS, but it suddenly complains, and I couldn't find any good examples on how to get it to work. All I found was a note on the documentation that I have to keep track of the vertexes myself.. Would there be any gain in going that way? Also is it possible (and would it be faster) to avoid creating a graph and calling add edge altogether and instead use a static graph with a visitor to determine edge cost, and if the edge is valid... I used the whole day yesterday to look for examples, but I couldn't find any using the boost library for that purpose.