{"id":31,"date":"2010-06-29T01:24:58","date_gmt":"2010-06-28T17:24:58","guid":{"rendered":"http:\/\/comzyh.gicp.net\/myblog\/?p=31"},"modified":"2010-10-19T16:50:32","modified_gmt":"2010-10-19T08:50:32","slug":"spfa","status":"publish","type":"post","link":"https:\/\/comzyh.com\/blog\/archives\/31\/","title":{"rendered":"SPFA"},"content":{"rendered":"<h2>\u7b97\u6cd5\u7b80\u4ecb<\/h2>\n<p>SPFA(Shortest Path Faster Algorithm)\u662f<a title=\"Bellman-Ford\u7b97\u6cd5\" href=\"http:\/\/www.nocow.cn\/index.php\/Bellman-Ford%E7%AE%97%E6%B3%95\">Bellman-Ford\u7b97\u6cd5<\/a>\u7684\u4e00\u79cd<a title=\"\u961f\u5217\" href=\"http:\/\/www.nocow.cn\/index.php\/%E9%98%9F%E5%88%97\">\u961f\u5217<\/a>\u5b9e\u73b0\uff0c\u51cf\u5c11\u4e86\u4e0d\u5fc5\u8981\u7684\u5197\u4f59\u8ba1\u7b97\u3002\u4e5f\u6709\u4eba\u8bf4SPFA\u672c\u6765\u5c31\u662fBellman-Ford\u7b97\u6cd5\uff0c\u73b0\u5728\u5e7f\u4e3a\u6d41\u4f20\u7684<a title=\"Bellman-Ford\u7b97\u6cd5\" href=\"http:\/\/www.nocow.cn\/index.php\/Bellman-Ford%E7%AE%97%E6%B3%95\">Bellman-Ford\u7b97\u6cd5<\/a>\u5b9e\u9645\u4e0a\u662f\u5c71\u5be8\u7248\u3002<\/p>\n<p><a name=\".E7.AE.97.E6.B3.95.E6.B5.81.E7.A8.8B\"><\/a><\/p>\n<h2>\u7b97\u6cd5\u6d41\u7a0b<\/h2>\n<p>\u7b97\u6cd5\u5927\u81f4\u6d41\u7a0b\u662f\u7528\u4e00\u4e2a\u961f\u5217\u6765\u8fdb\u884c\u7ef4\u62a4\u3002 \u521d\u59cb\u65f6\u5c06\u6e90\u52a0\u5165\u961f\u5217\u3002 \u6bcf\u6b21\u4ece\u961f\u5217\u4e2d\u53d6\u51fa\u4e00\u4e2a\u5143\u7d20\uff0c\u5e76\u5bf9\u6240\u6709\u4e0e\u4ed6\u76f8\u90bb\u7684\u70b9\u8fdb\u884c<a title=\"\u677e\u5f1b\" href=\"http:\/\/www.nocow.cn\/index.php\/%E6%9D%BE%E5%BC%9B\">\u677e\u5f1b<\/a>\uff0c\u82e5\u67d0\u4e2a\u76f8\u90bb\u7684\u70b9\u677e\u5f1b\u6210\u529f\uff0c\u5219\u5c06\u5176\u5165\u961f\u3002 \u76f4\u5230\u961f\u5217\u4e3a\u7a7a\u65f6\u7b97\u6cd5\u7ed3\u675f\u3002<\/p>\n<p>\u8fd9\u4e2a\u7b97\u6cd5\uff0c\u7b80\u5355\u7684\u8bf4\u5c31\u662f\u961f\u5217\u4f18\u5316\u7684bellman-ford,\u5229\u7528\u4e86\u6bcf\u4e2a\u70b9\u4e0d\u4f1a\u66f4\u65b0\u6b21\u6570\u592a\u591a\u7684\u7279\u70b9\u53d1\u660e\u7684\u6b64\u7b97\u6cd5<br \/>\n<!--more--><br \/>\nSPFA\u2014\u2014Shortest Path Faster Algorithm\uff0c\u5b83\u53ef\u4ee5\u5728O(kE)\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u5185\u6c42\u51fa\u6e90\u70b9\u5230\u5176\u4ed6\u6240\u6709\u70b9\u7684\u6700\u77ed\u8def\u5f84\uff0c\u53ef\u4ee5\u5904\u7406\u8d1f\u8fb9\u3002SPFA\u7684\u5b9e\u73b0\u751a\u81f3\u6bd4Dijkstra\u6216\u8005Bellman_Ford\u8fd8\u8981\u7b80\u5355\uff1a<\/p>\n<p>\u8bbeDist\u4ee3\u8868S\u5230I\u70b9\u7684\u5f53\u524d\u6700\u77ed\u8ddd\u79bb\uff0cFa\u4ee3\u8868S\u5230I\u7684\u5f53\u524d\u6700\u77ed\u8def\u5f84\u4e2dI\u70b9\u4e4b\u524d\u7684\u4e00\u4e2a\u70b9\u7684\u7f16\u53f7\u3002\u5f00\u59cb\u65f6Dist\u5168\u90e8\u4e3a+\u221e\uff0c\u53ea\u6709Dist[S]=0\uff0cFa\u5168\u90e8\u4e3a0\u3002<\/p>\n<p>\u7ef4\u62a4\u4e00\u4e2a\u961f\u5217\uff0c\u91cc\u9762\u5b58\u653e\u6240\u6709\u9700\u8981\u8fdb\u884c\u8fed\u4ee3\u7684\u70b9\u3002\u521d\u59cb\u65f6\u961f\u5217\u4e2d\u53ea\u6709\u4e00\u4e2a\u70b9S\u3002\u7528\u4e00\u4e2a\u5e03\u5c14\u6570\u7ec4\u8bb0\u5f55\u6bcf\u4e2a\u70b9\u662f\u5426\u5904\u5728\u961f\u5217\u4e2d\u3002<\/p>\n<p>\u6bcf\u6b21\u8fed\u4ee3\uff0c\u53d6\u51fa\u961f\u5934\u7684\u70b9v\uff0c\u4f9d\u6b21\u679a\u4e3e\u4ecev\u51fa\u53d1\u7684\u8fb9v-&gt;u\uff0c\u8bbe\u8fb9\u7684\u957f\u5ea6\u4e3alen\uff0c\u5224\u65adDist[v]+len\u662f\u5426\u5c0f\u4e8eDist[u]\uff0c\u82e5\u5c0f\u4e8e\u5219\u6539\u8fdbDist[u]\uff0c\u5c06Fa[u]\u8bb0\u4e3av\uff0c\u5e76\u4e14\u7531\u4e8eS\u5230u\u7684\u6700\u77ed\u8ddd\u79bb\u53d8\u5c0f\u4e86\uff0c\u6709\u53ef\u80fdu\u53ef\u4ee5\u6539\u8fdb\u5176\u5b83\u7684\u70b9\uff0c\u6240\u4ee5\u82e5u\u4e0d\u5728\u961f\u5217\u4e2d\uff0c\u5c31\u5c06\u5b83\u653e\u5165\u961f\u5c3e\u3002\u8fd9\u6837\u4e00\u76f4\u8fed\u4ee3\u4e0b\u53bb\u76f4\u5230\u961f\u5217\u53d8\u7a7a\uff0c\u4e5f\u5c31\u662fS\u5230\u6240\u6709\u7684\u6700\u77ed\u8ddd\u79bb\u90fd\u786e\u5b9a\u4e0b\u6765\uff0c\u7ed3\u675f\u7b97\u6cd5\u3002\u82e5\u4e00\u4e2a\u70b9\u5165\u961f\u6b21\u6570\u8d85\u8fc7n\uff0c\u5219\u6709\u8d1f\u6743\u73af\u3002<\/p>\n<p>SPFA \u5728\u5f62\u5f0f\u4e0a\u548c\u5bbd\u5ea6\u4f18\u5148\u641c\u7d22\u975e\u5e38\u7c7b\u4f3c\uff0c\u4e0d\u540c\u7684\u662f\u5bbd\u5ea6\u4f18\u5148\u641c\u7d22\u4e2d\u4e00\u4e2a\u70b9\u51fa\u4e86\u961f\u5217\u5c31\u4e0d\u53ef\u80fd\u91cd\u65b0\u8fdb\u5165\u961f\u5217\uff0c\u4f46\u662fSPFA\u4e2d\u4e00\u4e2a\u70b9\u53ef\u80fd\u5728\u51fa\u961f\u5217\u4e4b\u540e\u518d\u6b21\u88ab\u653e\u5165\u961f\u5217\uff0c\u4e5f\u5c31\u662f\u4e00\u4e2a\u70b9\u6539\u8fdb\u8fc7\u5176\u5b83\u7684\u70b9\u4e4b\u540e\uff0c\u8fc7\u4e86\u4e00\u6bb5\u65f6\u95f4\u53ef\u80fd\u672c\u8eab\u88ab\u6539\u8fdb\uff0c\u4e8e\u662f\u518d\u6b21\u7528\u6765\u6539\u8fdb\u5176\u5b83\u7684\u70b9\uff0c\u8fd9\u6837\u53cd\u590d\u8fed\u4ee3\u4e0b\u53bb\u3002\u8bbe\u4e00\u4e2a\u70b9\u7528\u6765\u4f5c\u4e3a\u8fed\u4ee3\u70b9\u5bf9\u5176\u5b83\u70b9\u8fdb\u884c\u6539\u8fdb\u7684\u5e73\u5747\u6b21\u6570\u4e3ak\uff0c\u6709\u529e\u6cd5\u8bc1\u660e\u5bf9\u4e8e\u901a\u5e38\u7684\u60c5\u51b5\uff0ck\u57282\u5de6\u53f3<\/p>\n<p>Dist[i]\uff1a\u5934\u5230i\u5f53\u524d\u6700\u5c0f\u8ddd\u79bb<\/p>\n<p>Cost[i,j]:\u90bb\u63a5\u77e9\u9635\uff0ci\u70b9\u5230j<\/p>\n<pre lang=\"pascal\">\r\nprocedure spfa;\r\nbegin\r\nfillchar(q,sizeof(q),0); h:=0; t:=0;\/\/\u961f\u5217\r\nfillchar(v,sizeof(v),false);\/\/v[i]\u5224\u65adi\u662f\u5426\u5728\u961f\u5217\u4e2d\r\nfor i:=1 to n do dist[i]:=maxint;\/\/\u521d\u59cb\u5316\u6700\u5c0f\u503c\r\n\r\ninc(t); q[t]:=1; v[1]:=true;\r\ndist[1]:=0;\/\/\u8fd9\u91cc\u628a1\u4f5c\u4e3a\u6e90\u70b9\r\n\r\nwhile h<>t do\/\/h\u961f\u5217\u5934\u4e0b\u6807\uff0ct\u961f\u5217\u5c3e\u4e0b\u6807\r\nbegin\r\n    h:=(h mod n)+1;x:=q[h];  v[x]:=false;\r\n    for i:=1 to n do\r\n     if (cost[x,i]>0)and(dist[x]+cost[x,i]<dist[i]) then\r\n     begin\r\n       dist[i]:=dist[x]+cost[x,i];\r\n       if not(v[i]) then\r\n       begin\r\n         t:=(t mod n)+1; q[t]:=i;v[i]:=true;\r\n       end;\r\n     end;\r\nend;\r\nend;\r\n<\/pre>\n<pre lang=\"C\" >\r\n#include <stdio.h>\r\n#include <string.h>\r\n#include <stdlib.h>\r\nint tab[1001][1001];\/\/\u4e34\u63a5\u8868 \r\nint v[1001];\/\/ \u662f\u5426\u8fdb\u8fc7\u961f\r\nint dis[1001];\/\/\u5f53\u524d\u6700\u77ed\u8def \r\nint n; \r\nvoid spfa(int p){\/\/x\u4e3a\u6e90\u70b9\r\n     int i,x;\r\n     int h,r;\r\n     int q[1001];\/\/SPFA\u961f\u5217,\u901a\u5e38\u60c5\u51b5\u4e0b\u6bcf\u4e2a\u5143\u7d20\u53ea\u8fdb\u4e00\u6b21 \r\n     memset (v,0,sizeof(v));\r\n     memset (dis,0,sizeof(dis));\r\n     for (i=1;i<=n;i++)dis[i]=0x4000000;\r\n     q[1]=p;\r\n     h=0;r=1;\r\n     dis[p]=0;\r\n     while (h<r){\r\n           h++;\r\n           x=q[h];\r\n           for (i=1;i<=n;i++)\r\n               if (dis[h]+tab[x][i]<dis[i]){\r\n                  dis[i]=dis[x]+tab[x][i];\r\n                  if (v[i]==0){\r\n                     q[++r]=i;\r\n                     v[i]=1;\r\n                     }\r\n                  }   \r\n           }\r\n           v[x]=0;\/\/\u51fa\u961f\u5217 \r\n     }\r\nint main(){\r\n    int i,j,m;\r\n    int f,t,l;\r\n    scanf(\"%d%d\",&#038;n,&#038;m);\r\n    memset(tab,0,sizeof(tab));\r\n    for (i=1;i<=n;i++)\r\n        for (j=1;j<=n;j++) \r\n            if (i!=j)tab[i][j]=0x40000001;\/\/maxlongint\r\n    for (i=1;i<=m;i++){\r\n        scanf(\"%d%d%d\",&#038;f,&#038;t,&#038;l);\r\n        tab[f][t]=l;\r\n        tab[t][f]=l;\r\n        }\r\n    spfa(1); \r\n    for (i=1;i<=n;i++) printf(\"%3d:%3d\\n\",i,dis[i]);\r\n    system(\"pause\");\r\n    }\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u7b97\u6cd5\u7b80\u4ecb SPFA(Shortest Path Faster Algorithm)\u662fBellman-Ford\u7b97 [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[9,30],"tags":[25,24],"class_list":["post-31","post","type-post","status-publish","format-standard","hentry","category-9","category-non-solution","tag-spfa","tag-24"],"jetpack_publicize_connections":[],"aioseo_notices":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/s6XQWE-spfa","jetpack-related-posts":[],"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts\/31","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/comments?post=31"}],"version-history":[{"count":0,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts\/31\/revisions"}],"wp:attachment":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/media?parent=31"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/categories?post=31"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/tags?post=31"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}