Na oko, po prostu słabo wybrałeś struktury danych:
vector<Dynamic_Graph<vertex_props, edge_props>::Vertex> doSprawdzenia;
doSprawdzenia.resize(graph.get_vertex_count());
for (auto j : doSprawdzenia) { //bottleneck ok. 50% czasu
if (i.get_connection_to_id() == j.get_id()) { //bottleneck ok. 20% czasu
isin = false;
break;
}
}
To zazwyczaj jest traktowane jako zbiór i robimy na nim typowe operacje na zbiorach, więc powinien być raczej std::set, std::unordered_set lub czymś podobnym przechowującym wierzchołki lub ich IDki (dla wydajności).
Podobnie, nie rozumiem tutaj też list linkowanych i kilku innych struktur.
Projekt samego API grafu też jest dziwny.
DjikstraAlgoritm(graph, graph.get_vertex(3));
...
cout << i << " " << graph.get_vertex(i).get_props().distance << "\t";
int id = graph.get_vertex(i).get_props().last;
Wywołanie funkcji zmienia wewnętrzny stan grafu, tak że każdy wierzchołek zna swoją odległość od wierzchołka 3...? Bardzo dziwnie to wygląda.