å¨äº¤éç½ç»ä¸ï¼å¸¸å¸¸ä¼æåºè®¸å¤è¿æ ·çé®é¢ï¼ä¸¤å°ä¹é´æ¯å¦æè·¯ç¸éï¼å¨æå¤æ¡éè·¯çæ
åµä¸ï¼åªä¸æ¡æè¿ï¼åªä¸æ¡è±è´¹æå°çã交éç½ç»å¯ä»¥ç¨å¸¦æå¾è¡¨ç¤ºï¼å¾ä¸é¡¶ç¹è¡¨ç¤ºåéï¼è¾¹è¡¨ç¤ºä¸¤åä¹é´çéè·¯ï¼è¾¹ä¸æå¼å¯è¡¨ç¤ºä¸¤åéé´çè·ç¦»ï¼äº¤éè´¹ç¨æéä¸æéçæ¶é´çã
ãã以ä¸æåºçé®é¢å°±æ¯å¸¦æå¾ä¸æ±æçè·¯å¾çé®é¢ï¼å³æ±ä¸¤ä¸ªé¡¶ç¹é´é¿åº¦æççè·¯å¾ã
ããæçè·¯å¾é®é¢çææ³å¾å¤ãå¨è¿éä»
讨论åæºæçè·¯å¾é®é¢ï¼å³å·²ç¥æåå¾(带æ)ï¼æ们å¸ææ¾åºä»æ个æºç¹SâVå°Gä¸å
¶ä½å顶ç¹çæçè·¯å¾ã
ããä¾å¦ï¼ä¸å¾(æåå¾G14)ï¼åå®ä»¥v1为æºç¹ï¼åå
¶å®å顶ç¹çæçè·¯å¾å¦ä¸è¡¨æ示ï¼
ãã
ããããããããããããããããããããå¾ G14
ããä»æåå¾å¯çåºï¼é¡¶ç¹v1å°v4çè·¯å¾æ3æ¡ï¼(v1,v2,v4)ï¼(v1,v4)ï¼(v1,v3,v2,v4 )ï¼å
¶è·¯å¾é¿åº¦åå«ä¸ºï¼15,20å10ãå æ¤v1å°v4çæçè·¯å¾ä¸º(v1,v3,v2,v4 )ã
ãã为äºåè¿°æ¹ä¾¿ï¼æ们æè·¯å¾ä¸çå¼å§ç¹ç§°ä¸ºæºç¹ï¼è·¯å¾çæåä¸ä¸ªé¡¶ç¹ä¸ºç»ç¹ã
ããé£ä¹ï¼å¦ä½æ±å¾ç»å®æåå¾çåæºæçè·¯å¾å¢ï¼è¿ªæ°æ¯ç¹æ(Dijkstra)æåºæè·¯å¾é¿åº¦éå¢äº§ç诸顶ç¹çæçè·¯å¾ç®æ³ï¼ç§°ä¹ä¸º
迪æ°æ¯ç¹æç®æ³ã
ãã迪æ°æ¯ç¹æç®æ³æ±æçè·¯å¾çå®ç°ææ³æ¯ï¼è®¾æåå¾G=(V,E)ï¼å
¶ä¸ï¼V={1,2,â¦,n}ï¼costæ¯è¡¨ç¤ºGç
é»æ¥ç©éµï¼cost[i][j] 表示æåè¾¹<i,j>çæãè¥ä¸åå¨æåè¾¹<i,j>ï¼åcost[i][j]çæ为
æ 穷大(è¿éåå¼ä¸º32767)ã设Sæ¯ä¸ä¸ªéåï¼å
¶ä¸çæ¯ä¸ªå
ç´ è¡¨ç¤ºä¸ä¸ªé¡¶ç¹ï¼ä»æºç¹å°è¿äºé¡¶ç¹çæçè·ç¦»å·²ç»æ±åºã设顶ç¹v1为æºç¹ï¼éåSçåæåªå
å«é¡¶ç¹v1ãæ°ç»distè®°å½ä»æºç¹å°å
¶ä»å顶ç¹å½åçæçè·ç¦»ï¼å
¶åå¼ä¸ºdist[i]=cost[v1][i]ï¼i=2,â¦,nãä»Sä¹å¤ç顶ç¹éåV-S ä¸éåºä¸ä¸ªé¡¶ç¹wï¼ä½¿dist[w]çå¼æå°ãäºæ¯ä»æºç¹å°è¾¾wåªéè¿S ä¸ç顶ç¹ï¼æwå å
¥éåSä¸è°æ´distä¸è®°å½çä»æºç¹å°V-Sä¸æ¯ä¸ªé¡¶ç¹vçè·ç¦»ï¼ä»åæ¥çdist[v] ådist[w]+cost[w][v]ä¸éæ©è¾å°çå¼ä½ä¸ºæ°çdist[v]ãéå¤ä¸è¿°è¿ç¨ï¼ç´å°Sä¸å
å«Vä¸å
¶ä½é¡¶ç¹çæçè·¯å¾ã
ããæç»ç»ææ¯ï¼Sè®°å½äºä»æºç¹å°è¯¥é¡¶ç¹åå¨æçè·¯å¾ç顶ç¹éåï¼æ°ç»distè®°å½äºä»æºç¹å° Vä¸å
¶ä½å顶ç¹ä¹é´çæçè·¯å¾ï¼pathæ¯æçè·¯å¾çè·¯å¾æ°ç»ï¼å
¶ä¸path[i] 表示ä»æºç¹å°é¡¶ç¹iä¹é´çæçè·¯å¾çå驱顶ç¹ã