Problems Base course RU

Built on

weighted graph

Articles

GRA Algorithm Dijkstra's algorithm Shortest paths from one vertex in a weighted graph without negative edges. O((V + E) log V) 3 problems GRA Algorithm A* Dijkstra with a hint of how far is left: the wave stretches towards the goal, and the path stays shortest. O((V + E) log V) 2 problems GRA Algorithm Bidirectional search Two Dijkstra waves towards each other: where to stop, how much is saved, and how to make it work with A*. O((V + E) log V) 2 problems GRA Algorithm The Bellman–Ford algorithm Shortest paths with negative edges and finding a negative cycle: V rounds over all edges. O(V · E) 2 problems GRA Algorithm Floyd–Warshall algorithm Shortest paths between all pairs of vertices in O(n³): dynamic programming over allowed transfers. O(n³) 2 problems GRA Algorithm Contraction hierarchies A navigator's precomputation: contract unimportant crossroads into shortcuts and find the path with two waves going up. O((V + E′) log V) 1 problem

Problems

A stop on the way Airports opening An honest hint At most k exchanges The courier's route A profitable round of exchanges Fire stations One free ride Queries over the tiers The shortest loop

Often together

shortest path 6 graph 6 interviews 5 heap 4 maps and navigation 4 classic 4 networks 3 heuristic 3 precomputation 2 dynamic programming 2 greedy 1 games 1