最短路

Emergency(PATA-1003) 题面 As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible. ...

简介 Johnson算法是求解多源最短路的算法之一，核心操作是re-weight，适用于不包含负环（负权回路）的图。时间复杂度$O(nm+nmlogm)$。 ...

简介 Floyd-Warshall算法是求解多源最短路的算法之一，核心思想是动态规划，适用于不包含负环（负权回路）的图。时间复杂度$O(n^{3})$，空间复杂度$O(n^{2})$。 ...

简介 Bellman-Ford算法是求解单源最短路的算法之一，适用于可包含负边权的有向和无向图，可以判断是否包含负环（注意，如果是包含负权回路则不存在最短路问题）。时间复杂度$O(nm)$。 ...

简介 Dijkstra算法是求解单源最短路的算法之一，核心思想是贪心，只适用于边权为正的无向和有向图。原复杂度$O(n^{2})$，优化后时间复杂度能到$O(mlog_{m})$。 ...