{"id":413,"date":"2026-04-19T18:19:35","date_gmt":"2026-04-19T10:19:35","guid":{"rendered":"https:\/\/jiangqvweihuan.cn\/?p=413"},"modified":"2026-04-19T18:19:35","modified_gmt":"2026-04-19T10:19:35","slug":"%e7%ae%97%e6%b3%95%e5%bf%83%e4%bc%a0%c2%b7%e6%9c%80%e7%9f%ad%e8%b7%af%e5%be%84","status":"publish","type":"post","link":"https:\/\/jiangqvweihuan.cn\/index.php\/2026\/04\/19\/%e7%ae%97%e6%b3%95%e5%bf%83%e4%bc%a0%c2%b7%e6%9c%80%e7%9f%ad%e8%b7%af%e5%be%84\/","title":{"rendered":"\u7b97\u6cd5\u5fc3\u4f20\u00b7\u6700\u77ed\u8def\u5f84"},"content":{"rendered":"\n<p>\u6700\u77ed\u8def\u5f84\u95ee\u9898\u662f\u56fe\u8bba\u4e2d\u6700\u7ecf\u5178\u3001\u5e94\u7528\u6700\u5e7f\u7684\u95ee\u9898\u4e4b\u4e00\u3002\u7b80\u5355\u8bf4\uff0c\u5c31\u662f\u7ed9\u5b9a\u4e00\u4e2a\u56fe\uff08\u7531\u70b9\u548c\u5e26\u6743\u8fb9\u7ec4\u6210\uff09\uff0c\u8981\u627e\u5230\u4efb\u610f\u4e24\u70b9\u4e4b\u95f4\u603b\u6743\u91cd\u6700\u5c0f\u7684\u8def\u5f84\u3002<br>\u4e00\u4e2a\u5f88\u5e38\u89c1\u7684\u73b0\u5b9e\u6848\u4f8b\uff0c\u662f\u5bfc\u822a\u8f6f\u4ef6\u662f\u5982\u4f55\u8ba1\u7b97\u51fa\u4e24\u5730\u4e4b\u95f4\u6700\u5feb\u7684\u8def\u7ebf\u7684<a href=\"https:\/\/blog.csdn.net\/2301_78967994\/article\/details\/154100411\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a>\u3002\u8fd9\u5c31\u662f\u5728\u6c42\u89e3\u6700\u77ed\u8def\u5f84\u95ee\u9898\u3002\u7406\u89e3\u8fd9\u4e2a\u95ee\u9898\u7684\u4e0d\u540c\u573a\u666f\uff0c\u662f\u5b66\u4e60\u7b97\u6cd5\u7684\u7b2c\u4e00\u6b65\u3002<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>\u5355\u6e90\u6700\u77ed\u8def\u5f84<\/strong>\uff1a\u6c42\u4ece\u56fe\u4e2d\u7684\u4e00\u4e2a\u7279\u5b9a\u8d77\u70b9\u5230\u6240\u6709\u5176\u4ed6\u70b9\u7684\u6700\u77ed\u8def\u5f84<a href=\"https:\/\/cloud.tencent.cn\/developer\/article\/1525973?from=15425&amp;frompage=seopage\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a>\u3002<\/li>\n\n\n\n<li><strong>\u591a\u6e90\uff08\u5168\u6e90\uff09\u6700\u77ed\u8def\u5f84<\/strong>\uff1a\u6c42\u56fe\u4e2d\u4efb\u610f\u4e24\u70b9\u4e4b\u95f4\u7684\u6700\u77ed\u8def\u5f84<a href=\"https:\/\/cloud.tencent.cn\/developer\/article\/2366695\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a>\u3002<\/li>\n\n\n\n<li><strong>\u786e\u5b9a\u7ec8\u70b9<\/strong>\uff1a\u5728\u65e0\u5411\u56fe\u4e2d\u4e0e\u5355\u6e90\u95ee\u9898\u4e00\u81f4\uff1b\u5728\u6709\u5411\u56fe\u4e2d\uff0c\u53ef\u4ee5\u901a\u8fc7\u53cd\u8f6c\u6240\u6709\u8fb9\u7684\u65b9\u5411\u8f6c\u5316\u4e3a\u5355\u6e90\u95ee\u9898<a href=\"https:\/\/cloud.tencent.cn\/developer\/article\/1525973?from=15425&amp;frompage=seopage\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a>\u3002<\/li>\n<\/ul>\n\n\n\n<p>\u5728\u6df1\u5165\u7ec6\u8282\u524d\uff0c\u53ef\u4ee5\u5148\u901a\u8fc7\u8fd9\u4e2a\u8868\u683c\u5bf9\u56db\u5927\u57fa\u7840\u7b97\u6cd5\u6709\u4e2a\u6574\u4f53\u628a\u63e1\uff1a<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><thead><tr><th>\u7b97\u6cd5<\/th><th>\u7c7b\u578b<\/th><th>\u65f6\u95f4\u590d\u6742\u5ea6<\/th><th>\u9002\u7528\u573a\u666f<\/th><th>\u4f18\u70b9<\/th><th>\u7f3a\u70b9<\/th><\/tr><\/thead><tbody><tr><td><strong>BFS<\/strong><\/td><td>\u5355\u6e90<\/td><td>O(N + M)<\/td><td>\u8fb9\u6743\u76f8\u7b49\u56fe<\/td><td>\u901f\u5ea6\u5feb\uff0c\u5b9e\u73b0\u7b80\u5355<\/td><td>\u65e0\u6cd5\u5904\u7406\u5e26\u6743\u56fe<\/td><\/tr><tr><td><strong>Floyd<\/strong><\/td><td>\u591a\u6e90<\/td><td>O(N\u00b3)<\/td><td>\u7a20\u5bc6\u56fe\u3001\u5c0f\u89c4\u6a21<\/td><td>\u5b9e\u73b0\u6781\u5176\u7b80\u5355<\/td><td>\u65f6\u95f4\u590d\u6742\u5ea6\u9ad8<\/td><\/tr><tr><td><strong>Dijkstra<\/strong><\/td><td>\u5355\u6e90<\/td><td>\u6734\u7d20O(N\u00b2)<br>\u5806\u4f18\u5316O(M log N)<\/td><td>\u975e\u8d1f\u6743\u56fe<\/td><td>\u9ad8\u6548\uff0c\u7a33\u5b9a<\/td><td>\u65e0\u6cd5\u5904\u7406\u8d1f\u6743\u8fb9<\/td><\/tr><tr><td><strong>Bellman-Ford<\/strong><\/td><td>\u5355\u6e90<\/td><td>O(N * M)<\/td><td>\u6709\u8d1f\u6743\u8fb9<\/td><td>\u53ef\u68c0\u6d4b\u8d1f\u73af<\/td><td>\u6548\u7387\u8f83\u4f4e<\/td><\/tr><tr><td><strong>SPFA<\/strong><\/td><td>\u5355\u6e90<\/td><td>\u5e73\u5747O(M)\uff0c\u6700\u574fO(N*M)<\/td><td>\u7a00\u758f\u56fe\u3001\u6709\u8d1f\u6743<\/td><td>\u901a\u5e38\u8f83\u5feb<\/td><td>\u4e0d\u7a33\u5b9a\uff0c\u6613\u88ab\u5361<\/td><\/tr><tr><td><strong>Johnson<\/strong><\/td><td>\u5168\u6e90<\/td><td>O(N * M * log N)<\/td><td>\u7a00\u758f\u56fe\u3001\u6709\u8d1f\u6743<\/td><td>\u7ed3\u5408Bellman-Ford\u548cDijkstra\u7684\u4f18\u70b9<\/td><td>\u5b9e\u73b0\u76f8\u5bf9\u590d\u6742<\/td><\/tr><tr><td><strong>A<\/strong>*<\/td><td>\u5355\u6e90\uff08\u542f\u53d1\u5f0f\uff09<\/td><td>\u89c6\u542f\u53d1\u51fd\u6570\u800c\u5b9a<\/td><td>\u6709\u76ee\u6807\u3001\u6709\u4f30\u8ba1<\/td><td>\u9ad8\u6548\uff0c\u5e38\u7528\u4e8e\u8def\u5f84\u89c4\u5212<\/td><td>\u9700\u8981\u8bbe\u8ba1\u542f\u53d1\u51fd\u6570<\/td><\/tr><tr><td><strong>\u53cc\u5411\u641c\u7d22<\/strong><\/td><td>\u5355\u6e90\uff08\u7279\u5b9a\uff09<\/td><td>\u89c6\u7b97\u6cd5\u800c\u5b9a<\/td><td>\u8fb9\u6743\u76f8\u7b49\u56fe\u3001\u8d77\u70b9\u7ec8\u70b9\u660e\u786e<\/td><td>\u5927\u5e45\u51cf\u5c11\u641c\u7d22\u7a7a\u95f4<\/td><td>\u5b9e\u73b0\u7a0d\u590d\u6742<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">\u4e00\u3001\u57fa\u7840\u7b51\u57fa (Foundation)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">1. DFS\/BFS (\u9002\u7528\uff1a\u65e0\u6743\u56fe\/\u8fb9\u6743\u4e3a1)<\/h3>\n\n\n\n<p>\u5f53\u56fe\u4e2d\u6240\u6709\u8fb9\u7684\u6743\u503c\u76f8\u7b49\uff08\u901a\u5e38\u4e3a1\uff09\uff0c\u5373\u5bfb\u627e\u8df3\u6570\u6700\u5c11\u7684\u8def\u5f84\u65f6\uff0c\u6700\u76f4\u63a5\u7684\u65b9\u6cd5\u5c31\u662f<strong>\u5e7f\u5ea6\u4f18\u5148\u641c\u7d22 (BFS)<\/strong><a href=\"https:\/\/cloud.tencent.cn\/developer\/article\/1525973?from=15425&amp;frompage=seopage\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a>\u3002BFS\u7684\u7279\u6027\u786e\u4fdd\u4e86\u7b2c\u4e00\u6b21\u8bbf\u95ee\u5230\u67d0\u4e2a\u8282\u70b9\u65f6\uff0c\u6240\u7ecf\u8fc7\u7684\u8def\u5f84\u5c31\u662f\u6700\u77ed\u7684\u3002<\/p>\n\n\n\n<p>\u4ee3\u7801\u6a21\u677f\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;bits\/stdc++.h>\nusing namespace std;\n\nvector&lt;int> bfsShortestPath(vector&lt;vector&lt;int>>&amp; graph, int start, int end) {\n    int n = graph.size();\n    vector&lt;int> dist(n, -1), prev(n, -1);\n    queue&lt;int> q;\n\n    dist&#91;start] = 0;\n    q.push(start);\n\n    while (!q.empty()) {\n        int u = q.front(); q.pop();\n        if (u == end) break; \/\/ \u627e\u5230\u76ee\u6807\uff0c\u63d0\u524d\u9000\u51fa\n\n        for (int v : graph&#91;u]) {\n            if (dist&#91;v] == -1) { \/\/ \u672a\u8bbf\u95ee\u8fc7\n                dist&#91;v] = dist&#91;u] + 1;\n                prev&#91;v] = u;\n                q.push(v);\n            }\n        }\n    }\n\n    \/\/ \u6784\u5efa\u8def\u5f84\n    vector&lt;int> path;\n    for (int at = end; at != -1; at = prev&#91;at]) path.push_back(at);\n    reverse(path.begin(), path.end());\n    return path;\n}<\/code><\/pre>\n\n\n\n<p>\u63a8\u8350\u4e60\u9898\uff1a<a href=\"https:\/\/ac.nowcoder.com\/acm\/problem\/205089\">\u725b\u59b9\u7684\u82f9\u679c\u6811<\/a><\/p>\n\n\n\n<h3 class=\"wp-block-heading\">2. Floyd\u7b97\u6cd5<\/h3>\n\n\n\n<p>Floyd\u7b97\u6cd5\uff08\u5f17\u6d1b\u4f0a\u5fb7\u7b97\u6cd5\uff09\u91c7\u7528<strong>\u52a8\u6001\u89c4\u5212<\/strong>\u601d\u60f3\uff0c\u6c42\u89e3\u4efb\u610f\u4e24\u70b9\u95f4\u7684\u6700\u77ed\u8def\u5f84\u3002\u5b83\u7684\u6838\u5fc3\u662f\u201c\u63d2\u70b9\u6cd5\u201d\uff1a\u9010\u6b65\u5141\u8bb8\u6bcf\u4e2a\u9876\u70b9\u4f5c\u4e3a\u4e2d\u8f6c\u70b9\uff0c\u68c0\u67e5\u662f\u5426\u80fd\u7f29\u77ed\u4e24\u70b9\u95f4\u7684\u8ddd\u79bb<a href=\"https:\/\/cloud.tencent.cn\/developer\/article\/2366695\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a>\u3002<\/p>\n\n\n\n<p>\u5b9e\u73b0\u4ee3\u7801\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;bits\/stdc++.h>\nusing namespace std;\n\nconst int INF = 0x3f3f3f3f; \/\/ \u7528\u4e00\u4e2a\u5f88\u5927\u7684\u6570\u8868\u793a\u201c\u65e0\u7a77\u5927\u201d\nint dist&#91;510]&#91;510]; \/\/ \u90bb\u63a5\u77e9\u9635\u5b58\u50a8\u8ddd\u79bb\n\nvoid floyd(int n) {\n    for (int k = 1; k &lt;= n; k++) \/\/ \u679a\u4e3e\u4e2d\u95f4\u70b9\n        for (int i = 1; i &lt;= n; i++) \/\/ \u679a\u4e3e\u8d77\u70b9\n            for (int j = 1; j &lt;= n; j++) \/\/ \u679a\u4e3e\u7ec8\u70b9\n                if (dist&#91;i]&#91;k] &lt; INF &amp;&amp; dist&#91;k]&#91;j] &lt; INF) \/\/ \u9632\u6b62\u6ea2\u51fa\n                    dist&#91;i]&#91;j] = min(dist&#91;i]&#91;j], dist&#91;i]&#91;k] + dist&#91;k]&#91;j]);\n}\n\nint main() {\n    int n, m;\n    cin >> n >> m;\n    \/\/ \u521d\u59cb\u5316\u90bb\u63a5\u77e9\u9635\n    memset(dist, 0x3f, sizeof(dist));\n    for (int i = 1; i &lt;= n; i++) dist&#91;i]&#91;i] = 0;\n\n    for (int i = 0; i &lt; m; i++) {\n        int u, v, w;\n        cin >> u >> v >> w;\n        dist&#91;u]&#91;v] = min(dist&#91;u]&#91;v], w); \/\/ \u9632\u6b62\u91cd\u8fb9\n    }\n\n    floyd(n);\n    \/\/ \u8f93\u51fa\u7ed3\u679c...\n    return 0;\n}<\/code><\/pre>\n\n\n\n<p>\u4e60\u9898\u63a8\u8350\uff1a<a href=\"https:\/\/www.luogu.com.cn\/problem\/P2910\">P2910 [USACO08OPEN] Clear And Present Danger S &#8211; \u6d1b\u8c37<\/a><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u4e00\u3001\u5355\u6e90\u6b63\u6743\u4e4b\u738b\u00a0<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">1. Dijkstra\u7b97\u6cd5<\/h3>\n\n\n\n<p>Dijkstra\u7b97\u6cd5\uff08\u8fea\u6770\u65af\u7279\u62c9\u7b97\u6cd5\uff09\u662f\u89e3\u51b3<strong>\u975e\u8d1f\u6743\u56fe<\/strong>\u5355\u6e90\u6700\u77ed\u8def\u95ee\u9898\u7684\u9996\u9009<a href=\"https:\/\/blog.csdn.net\/2301_78967994\/article\/details\/154100411\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a>\u3002\u5b83\u91c7\u7528<strong>\u8d2a\u5fc3\u7b56\u7565<\/strong>\uff1a\u7ef4\u62a4\u4e00\u4e2a\u201c\u5df2\u786e\u5b9a\u6700\u77ed\u8def\u5f84\u201d\u7684\u96c6\u5408\uff0c\u6bcf\u6b21\u4ece\u201c\u672a\u786e\u5b9a\u201d\u96c6\u5408\u4e2d\u9009\u51fa\u4e00\u4e2a\u8ddd\u79bb\u6e90\u70b9\u6700\u8fd1\u7684\u70b9\uff0c\u52a0\u5165\u201c\u5df2\u786e\u5b9a\u201d\u96c6\u5408\u5e76\u5c1d\u8bd5\u7528\u5b83\u53bb\u677e\u5f1b\u5176\u90bb\u5c45\u7684\u8ddd\u79bb<a href=\"https:\/\/cloud.tencent.cn\/developer\/article\/1525973?from=15425&amp;frompage=seopage\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a>\u3002<\/p>\n\n\n\n<p>\u8fd9\u662f\u7ade\u8d5b\u4e2d\u6700\u5e38\u7528\u7684\u5199\u6cd5\uff0c\u4f7f\u7528\u94fe\u5f0f\u524d\u5411\u661f\u5b58\u56fe\uff0c\u6548\u7387\u5f88\u9ad8\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\nusing pii = pair&lt;ll, int>;\n\nconst int N = 1e5 + 10, M = 2e5 + 10; \/\/ \u6839\u636e\u9898\u76ee\u8c03\u6574\u5927\u5c0f\nconst ll INF = 0x3f3f3f3f3f3f3f3f;\n\nint n, m, s;\nint head&#91;N], cnt;\nll dist&#91;N];\nbool vis&#91;N];\n\nstruct Edge {\n    int to, nxt;\n    ll w;\n} e&#91;M];\n\nvoid addEdge(int u, int v, ll w) {\n    e&#91;++cnt] = {v, head&#91;u], w};\n    head&#91;u] = cnt;\n}\n\nvoid dijkstra(int s) {\n    memset(dist, 0x3f, sizeof(dist));\n    dist&#91;s] = 0;\n    priority_queue&lt;pii, vector&lt;pii>, greater&lt;pii>> pq; \/\/ \u5c0f\u6839\u5806\n    pq.push({0, s});\n\n    while (!pq.empty()) {\n        auto &#91;d, u] = pq.top(); pq.pop();\n        if (vis&#91;u]) continue;\n        vis&#91;u] = true;\n\n        for (int i = head&#91;u]; i; i = e&#91;i].nxt) {\n            int v = e&#91;i].to;\n            ll w = e&#91;i].w;\n            if (dist&#91;v] > dist&#91;u] + w) {\n                dist&#91;v] = dist&#91;u] + w;\n                pq.push({dist&#91;v], v}); \/\/ \u5c06\u66f4\u65b0\u540e\u7684\u8282\u70b9\u52a0\u5165\u5806\n            }\n        }\n    }\n}\n\nint main() {\n    cin >> n >> m >> s;\n    for (int i = 1; i &lt;= m; i++) {\n        int u, v; ll w;\n        cin >> u >> v >> w;\n        addEdge(u, v, w);\n    }\n    dijkstra(s);\n    for (int i = 1; i &lt;= n; i++) cout &lt;&lt; dist&#91;i] &lt;&lt; \" \\n\"&#91;i == n];\n    return 0;\n}<\/code><\/pre>\n\n\n\n<p>\u63a8\u8350\u4e60\u9898\uff1a<br><a href=\"https:\/\/www.luogu.com.cn\/problem\/P3371\">P3371 \u3010\u6a21\u677f\u3011\u5355\u6e90\u6700\u77ed\u8def\u5f84\uff08\u5f31\u5316\u7248\uff09 &#8211; \u6d1b\u8c37<\/a><br><a href=\"https:\/\/www.luogu.com.cn\/problem\/P4779\">P4779 \u3010\u6a21\u677f\u3011\u5355\u6e90\u6700\u77ed\u8def\u5f84\uff08\u6807\u51c6\u7248\uff09 &#8211; \u6d1b\u8c37<\/a><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u4e09\u3001\u62e5\u62b1\u8d1f\u6743<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">1. Bellman-Ford\u7b97\u6cd5<\/h3>\n\n\n\n<p>\u5f53\u56fe\u4e2d\u5b58\u5728\u8d1f\u6743\u8fb9\u65f6\uff0cDijkstra\u5c31\u5931\u6548\u4e86\u3002<strong>Bellman-Ford\u7b97\u6cd5<\/strong>\uff08\u8d1d\u5c14\u66fc-\u798f\u7279\u7b97\u6cd5\uff09\u901a\u8fc7\u53cd\u590d\u5bf9\u6240\u6709\u8fb9\u8fdb\u884c\u201c\u677e\u5f1b\u201d\u64cd\u4f5c\u6765\u5bfb\u627e\u6700\u77ed\u8def\u5f84\u3002\u5b83\u662f\u6700\u901a\u7528\u7684\u5355\u6e90\u6700\u77ed\u8def\u7b97\u6cd5\uff0c\u5e76\u80fd\u68c0\u6d4b<strong>\u8d1f\u6743\u73af<\/strong>\uff08\u4e00\u79cd\u4e0d\u5b58\u5728\u6700\u77ed\u8def\u5f84\u7684\u56fe\uff09\u3002<\/p>\n\n\n\n<p>\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;bits\/stdc++.h>\nusing namespace std;\n\nstruct Edge {\n    int u, v, w;\n};\nconst int N = 1e5 + 10, INF = 0x3f3f3f3f;\nvector&lt;Edge> edges;\nint dist&#91;N];\n\nbool bellmanFord(int n, int m, int s) {\n    memset(dist, 0x3f, sizeof(dist));\n    dist&#91;s] = 0;\n\n    \/\/ \u6700\u591a\u677e\u5f1b n-1 \u6b21\n    for (int i = 1; i &lt; n; i++) {\n        bool updated = false;\n        for (auto&amp; e : edges) {\n            if (dist&#91;e.u] &lt; INF &amp;&amp; dist&#91;e.v] > dist&#91;e.u] + e.w) {\n                dist&#91;e.v] = dist&#91;e.u] + e.w;\n                updated = true;\n            }\n        }\n        if (!updated) break; \/\/ \u82e5\u672c\u8f6e\u6ca1\u6709\u66f4\u65b0\uff0c\u5219\u63d0\u524d\u7ed3\u675f\n    }\n\n    \/\/ \u7b2c n \u6b21\u677e\u5f1b\uff0c\u7528\u4e8e\u68c0\u6d4b\u8d1f\u73af\n    for (auto&amp; e : edges) {\n        if (dist&#91;e.u] &lt; INF &amp;&amp; dist&#91;e.v] > dist&#91;e.u] + e.w) {\n            return true; \/\/ \u5b58\u5728\u8d1f\u73af\n        }\n    }\n    return false; \/\/ \u65e0\u8d1f\u73af\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">2. SPFA\u7b97\u6cd5<\/h3>\n\n\n\n<p>SPFA (Shortest Path Faster Algorithm) \u662fBellman-Ford\u7b97\u6cd5\u7684\u961f\u5217\u4f18\u5316\u7248\u672c\u3002\u5b83\u53ea\u5bf9\u201c\u8ddd\u79bb\u88ab\u66f4\u65b0\u8fc7\u201d\u7684\u8282\u70b9\u8fdb\u884c\u677e\u5f1b\uff0c\u5e73\u5747\u60c5\u51b5\u4e0b\u6548\u7387\u5f88\u9ad8\uff0c\u4f46\u5728\u6781\u7aef\u6570\u636e\u4e0b\u53ef\u80fd\u9000\u5316<a href=\"https:\/\/blog.csdn.net\/weixin_51566349\/article\/details\/126830894\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a>\u3002<\/p>\n\n\n\n<p>\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>SPFA (Shortest Path Faster Algorithm) \u662fBellman-Ford\u7b97\u6cd5\u7684\u961f\u5217\u4f18\u5316\u7248\u672c\u3002\u5b83\u53ea\u5bf9\u201c\u8ddd\u79bb\u88ab\u66f4\u65b0\u8fc7\u201d\u7684\u8282\u70b9\u8fdb\u884c\u677e\u5f1b\uff0c\u5e73\u5747\u60c5\u51b5\u4e0b\u6548\u7387\u5f88\u9ad8\uff0c\u4f46\u5728\u6781\u7aef\u6570\u636e\u4e0b\u53ef\u80fd\u9000\u5316\u3002<\/code><\/pre>\n\n\n\n<p>\u63a8\u8350\u4e60\u9898\uff1a<br><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u6700\u77ed\u8def\u5f84\u95ee\u9898\u662f\u56fe\u8bba\u4e2d\u6700\u7ecf\u5178\u3001\u5e94\u7528\u6700\u5e7f\u7684\u95ee\u9898\u4e4b\u4e00\u3002\u7b80\u5355\u8bf4\uff0c\u5c31\u662f\u7ed9\u5b9a\u4e00\u4e2a\u56fe\uff08\u7531\u70b9\u548c\u5e26\u6743\u8fb9\u7ec4\u6210\uff09\uff0c\u8981\u627e\u5230\u4efb\u610f\u4e24\u70b9\u4e4b\u95f4 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":156,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[18,1,15,12],"tags":[],"class_list":["post-413","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-graph-theory","category-article","category-algorithm-template","category-programming-algorithm-road"],"_links":{"self":[{"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/posts\/413","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/comments?post=413"}],"version-history":[{"count":2,"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/posts\/413\/revisions"}],"predecessor-version":[{"id":434,"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/posts\/413\/revisions\/434"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/media\/156"}],"wp:attachment":[{"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/media?parent=413"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/categories?post=413"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/tags?post=413"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}