{"id":621,"date":"2005-08-29T08:39:03","date_gmt":"2005-08-29T00:39:03","guid":{"rendered":"http:\/\/pony.hk\/?p=621"},"modified":"2020-09-28T08:50:33","modified_gmt":"2020-09-28T00:50:33","slug":"%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84-%e6%9c%80%e7%9f%ad%e8%b7%af%e5%be%84-dijkstra%e7%ae%97%e6%b3%95","status":"publish","type":"post","link":"https:\/\/lnmp.ivan.xin\/?p=621","title":{"rendered":"\u6570\u636e\u7ed3\u6784--*\u6700\u77ed\u8def\u5f84--*dijkstra\u7b97\u6cd5"},"content":{"rendered":"

C\u770b\u5b8c\u4e86\uff0c\u6570\u636e\u7ed3\u6784\u4e5f\u5feb\u4e86\uff0c\u7b97\u6cd5\u770b\u7684\u4e0d\u723d\uff0c\u8fd8\u662f\u81ea\u5df1\u91cd\u65b0\u5199\u4e00\u904d\u7a0b\u5e8f\u6765\u5fc3\u91cc\u6bd4\u8f83\u584c\u5b9e<\/p>\n

\uff03i nclude<iostream.h>
\n\uff03i nclude<cstdlib>
\n#define max 6\/\/\u9876\u70b9\u7684\u6570\u91cf
\n#define big 10000
\nvoid dijkstra(int vx,int AA[],int D[],int LJ[][max]);
\nint main()
\n{
\nint AA[max];\/\/\u628a\u9876\u70b9\u5206\u6210\u4e24\u7c7b\uff0c1\u8868\u793a\u5df2\u7ecf\u5728\u6700\u5c0f\u8def\u5f84\u91cc\u7684\u9876\u70b9\uff0c0\u8868\u793a\u8fd8\u6ca1\u6709\u5728\u6700\u5c0f\u8def\u5f84\u91cc\u7684\u9876\u70b9
\nint LJ[max][max];\/\/\u90bb\u63a5\u77e9\u9635
\nint D[max];\/\/\u8bb0\u5f55\u5230\u6bcf\u4e2a\u9876\u70b9\u7684\u6700\u5c0f\u4ee3\u4ef7
\nint i,j,vx;
\nfor(i=0;i<max;i++)
\nfor(j=0;j<max;j++)
\nLJ[j]=big;
\nLJ[0][2]=10;LJ[0][4]=30;LJ[0][5]=100;LJ[1][2]=5;LJ[2][3]=50;LJ[3][5]=10;LJ[4][3]=20;LJ[4][5]=60;
\nfor(vx=0;vx<max;vx++)\/\/\u5bf9\u6bcf\u4e2a\u9876\u70b9\u8c03\u7528dijkstra\u7b97\u6cd5\uff0c\u4ece\u800c\u4ea7\u751f\u4ece\u9876\u70b9vx\u5230\u5230\u5404\u9876\u70b9\u7684\u6700\u5c0f\u8def\u5f84\uff0c\u9002\u5408\u4e8e\u6709\u5411\u56fe\uff0c\u5982\u679c\u662f\u65e0\u5411\u56fe\uff0c\u8fd8\u8981\u6bd4\u8f83i->j\u548cj->i\u7684\u6700\u77ed\u8def\u5f84\u54ea\u4e2a\u66f4\u5c0f
\n{
\nfor(i=0;i<max;i++)
\nD=LJ[vx];\/\/\u521d\u59cb\u5316\u6700\u5c0f\u4ee3\u4ef7
\nfor(i=0;i<max;i++)\/\/\u521d\u59cb\u5316\u9876\u70b9\u5206\u7c7b
\nAA=0;
\nAA[vx]=1;
\ndijkstra(vx,AA,D,LJ);
\ncout<<endl;
\n}
\nsystem(\"pause\");
\nreturn 0;
\n}
\nvoid dijkstra(int vx,int AA[],int D[],int LJ[][max])
\n{
\nint i,j,k;
\nfor(k=0;k<max;k++)\/\/\u6bcf\u6b21\u6c42\u51fa\u4e00\u6761\u6700\u5c0f\u8def\u5f84
\n{
\nfor(i=0;i<max;i++)\/\/\u672c\u5c42\u5faa\u73af\u662f\u6c42\u51fa\u8fd9\u65f6\u6bcf\u4e2a\u4e0d\u5728\u6700\u5c0f\u8def\u5f84\u9876\u70b9\u96c6\u91cc\u7684\u9876\u70b9\u5230\u9876\u70b9vx\u7684\u6700\u5c0f\u4ee3\u4ef7
\nfor(j=0;j<max;j++)\/\/\u672c\u5c42\u5faa\u73af\u662f\u6c42\u51fa\u9876\u70b9i\u901a\u8fc7\u6700\u5c0f\u8def\u5f84\u9876\u70b9\u96c6\u5230\u9876\u70b9vx\u7684\u6700\u5c0f\u8def\u5f84
\nif(LJ[j]+D[j]<D && AA[j]==1 && AA==0)
\nD=LJ[j]+D[j];
\nint small=vx,value=big+1;\/\/\u521d\u59cb\u5316\uff0c\u9632\u6b62\u51fa\u9519
\nfor(j=0;j<max;j++)\/\/\u6c42\u51fa\u672c\u6b21\u5faa\u73af\u4ea7\u751f\u7684\u6700\u5c0f\u8def\u5f84
\nif(D[j]<value && AA[j]==0)
\n{
\nvalue=D[j];
\nsmall=j;
\n}
\nAA[small]=1;\/\/\u8fd9\u6b21\u6c42\u51fa\u7684\u6700\u5c0f\u8def\u5f84\u662f\u9876\u70b9vx\u5230\u9876\u70b9small\u7684\uff0c\u6240\u4ee5\u8981\u628a\u9876\u70b9small\u4ece\u4e0d\u662f\u6700\u5c0f\u8def\u5f84\u91cc\u7684\u9876\u70b9\uff0c\u53d8\u6210\u6700\u5c0f\u8def\u5f84\u91cc\u7684\u9876\u70b9
\n}
\nfor(i=0;i<max;i++)
\n{
\nif(i==vx);
\nelse if(D==big)
\ncout<<vx<<\"->\"<<i<<\"\uff1a\u6ca1\u6709\u901a\u8def\"<<endl;
\nelse
\ncout<<vx<<\"->\"<<i<<\"\u6700\u5c0f\u8def\u5f84\u4e3a\uff1a\"<<D<<endl;
\n}
\n}<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"

C\u770b\u5b8c\u4e86\uff0c\u6570\u636e\u7ed3\u6784\u4e5f\u5feb\u4e86\uff0c\u7b97\u6cd5\u770b\u7684\u4e0d\u723d\uff0c\u8fd8\u662f\u81ea\u5df1\u91cd\u65b0\u5199\u4e00\u904d\u7a0b\u5e8f\u6765\u5fc3\u91cc\u6bd4\u8f83\u584c\u5b9e \uff03i nclude<ios...<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[28325],"tags":[],"class_list":["post-621","post","type-post","status-publish","format-standard","hentry","category-c"],"_links":{"self":[{"href":"https:\/\/lnmp.ivan.xin\/index.php?rest_route=\/wp\/v2\/posts\/621","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lnmp.ivan.xin\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lnmp.ivan.xin\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lnmp.ivan.xin\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/lnmp.ivan.xin\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=621"}],"version-history":[{"count":5,"href":"https:\/\/lnmp.ivan.xin\/index.php?rest_route=\/wp\/v2\/posts\/621\/revisions"}],"predecessor-version":[{"id":626,"href":"https:\/\/lnmp.ivan.xin\/index.php?rest_route=\/wp\/v2\/posts\/621\/revisions\/626"}],"wp:attachment":[{"href":"https:\/\/lnmp.ivan.xin\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=621"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lnmp.ivan.xin\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=621"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lnmp.ivan.xin\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=621"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}