Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"workbook":{"problemsBrief":"{\"洛谷-P4479\":[\"第k大斜率\",490,\"BJWC2018\"],\"洛谷-P1119\":[\"灾后重建\",28004,null],\"POJ-3259\":[\"Wormholes\",19365,\"\\u003cdiv class\\u003d\\\"ptx\\\" lang\\u003d\\\"en-US\\\"\\u003e\\u003ca href\\u003d\\\"http://poj.org/searchproblem?field\\u003dsource\\u0026amp;key\\u003dUSACO+2006+December+Gold\\\"\\u003eUSACO 2006 December Gold\\u003c/a\\u003e\\u003c/div\\u003e\"],\"POJ-1125\":[\"Stockbroker Grapevine\",18387,\"\\u003cdiv class\\u003d\\\"ptx\\\" lang\\u003d\\\"en-US\\\"\\u003e\\u003ca href\\u003d\\\"http://poj.org/searchproblem?field\\u003dsource\\u0026amp;key\\u003dSouthern+African+2001\\\"\\u003eSouthern African 2001\\u003c/a\\u003e\\u003c/div\\u003e\"],\"POJ-3621\":[\"Sightseeing Cows\",2362,\"\\u003cdiv class\\u003d\\\"ptx\\\" lang\\u003d\\\"en-US\\\"\\u003e\\u003ca href\\u003d\\\"http://poj.org/searchproblem?field\\u003dsource\\u0026amp;key\\u003dUSACO+2007+December+Gold\\\"\\u003eUSACO 2007 December Gold\\u003c/a\\u003e\\u003c/div\\u003e\"],\"洛谷-B3647\":[\"Floyd\",12364,\"模板\"],\"POJ-2449\":[\"Remmarguts\\u0027 Date\",6326,\"\\u003cdiv class\\u003d\\\"ptx\\\" lang\\u003d\\\"en-US\\\"\\u003e\\u003ca href\\u003d\\\"http://poj.org/searchproblem?field\\u003dsource\\u0026amp;key\\u003dPOJ+Monthly\\\"\\u003ePOJ Monthly\\u003c/a\\u003e,Zeyuan Zhu\\u003c/div\\u003e\"],\"HDU-2544\":[\"最短路\",26573,\"\\u003cdiv class\\u003d\\\"panel_content\\\"\\u003e \\u003ca href\\u003d\\\"https://acm.hdu.edu.cn/search.php?field\\u003dproblem\\u0026amp;key\\u003dUESTC+6th+Programming+Contest+Online\\u0026amp;source\\u003d1\\u0026amp;searchmode\\u003dsource\\\"\\u003e UESTC 6th Programming Contest Online \\u003c/a\\u003e \\u003c/div\\u003e\"],\"洛谷-P1144\":[\"最短路计数\",40095,null],\"洛谷-P3385\":[\"负环\",38644,\"模板\"],\"CodeForces-580D\":[\"Kefa and Dishes\",10466,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/580\\\"\\u003eCodeforces Round 321 (Div. 2)\\u003c/a\\u003e\"],\"洛谷-P1462\":[\"通往奥格瑞玛的道路\",19454,null]}","joined":false,"groups":{}},"managingGroups":{},"author":"lxnhb","updateTime":1711793169000,"title":"最短路题单","dislikeCnt":0,"content":"# 最短路题单\n\n## 一、多源最短路算法\n\n### 1、Floyd\n\nFloyd求取所有点对之间的最短路\n\n优点:代码简洁,三层for循环即可。\n\n缺点:时间复杂度为$O(n^3)$,意味着只能用于n\u003c300规模的图\n\n- Floyd允许有负边,但不允许有负环,但是又可以判断负环,即dp[i] [i]\u003c0,不过通常负环判断使用Bellman-Ford或SPFA\n\n[problem:洛谷-B3647]\n[problem:洛谷-P1119]\n[problem:CodeForces-580D]\n[problem:POJ-1125]\n## 二、单源最短路算法\n### 1、Dijkstra\n算法思路简单来说就是BFS+贪心(贪心用优先队列来完成)\n时间复杂度分析:\n- 设图有n个点,m条边,优先队列大多使用堆来模拟,完成一次存取操作时间复杂度为$O(log_2n)$,一共向队列插入m次,时间复杂度为$O(mlog_2n)$,取出n次,每次更新这个点的所有邻居到起点的距离,假设一个点平均有k个邻居,时间复杂度为$O(nklog_2n)$,故总时间复杂度为$O(mlog_2n+nklog_2n)\\approx O(mlog_2n)$。\n\n优点:计算单源最短路效率最高的算法\n缺点:边权不能为负,言外之意--无法判断负环\n[problem:洛谷-P4479]\n[problem:洛谷-P1144]\n[problem:洛谷-P1462]\n[problem:POJ-2449] A* 算法\n### 2、Bellman-Ford\n算法原理:原理是对图进行V-1次松弛操作,得到所有可能的最短路径。具体的来说就是问路模型,一个点不需要知道到s的完整路径,只需要知道往哪个邻居走能到达起点,并且路最近。\n时间复杂度分析:\n- 每轮能确定一个点的最短路径,n个点共进行n轮计算,每轮需要检查所有m条边。总复杂度为$O(nm)$\n\n建议用结构体数组存图,避免大量空间浪费。\n优点:可以判断负环\n缺点:效率低\n[problem:洛谷-P3385]\n[problem:POJ-3259]\n### 3、SPFA\n基于Bellman-Ford的原理,可以使用队列优化,只将每一轮更新过的邻居入队即可,避免许多没有必要的计算。\n优点:可以判断负环\n缺点:不稳定,最差情况下时间复杂度为$O(nm)$\n[problem:HDU-2544]\n[problem:POJ-3621] SPFA和最优比率环\n\n\n\n\n","threadId":188337,"likeCnt":0,"createTime":1711786736000,"isWorkbook":true,"viewCnt":99,"openness":2,"fav":false,"id":4774,"trustable":false}