Skip to content

Instantly share code, notes, and snippets.

@kbegiedza

kbegiedza/Shortest_path_for_friend.cpp

Last active May 20, 2019 18:30
Show Gist options
  • Save kbegiedza/40b9ece548de131a0c8fe924b5cb578f to your computer and use it in GitHub Desktop.
Save kbegiedza/40b9ece548de131a0c8fe924b5cb578f to your computer and use it in GitHub Desktop.
Download ZIP
Dijkstra shortest path
Raw
Shortest_path_for_friend.cpp
double Graph::shortest_path(unsigned int src, unsigned int dest)
{
std::vector<bool> visited(capacity_, false);
std::vector<double> distance(capacity_, std::numeric_limits<double>::max());
auto cmp = [&distance](unsigned int& l, unsigned int& r) -> bool { return (distance[l] > distance[r]); };
std::priority_queue<unsigned int, std::vector<unsigned int>, decltype(cmp)> q (cmp);
q.push(src);
distance[src] = 0;
while(!q.empty())
{
unsigned int vert = q.top();
q.pop();
if (visited[vert])
{
continue;
}
for(auto iter = adjacency_list_[vert].begin(); iter != adjacency_list_[vert].end();++iter)
{
if (visited[iter->destination])
{
continue;
}
q.push(iter->destination);
distance[iter->destination] = std::min(distance[vert] + iter->weight, distance[iter->destination]);
}
visited[vert] = true;
}
return distance[dest];
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment