Dijkstraç®æ³çåºæ¬æè·¯æ¯ï¼å设æ¯ä¸ªç¹é½æä¸å¯¹æ å· (dj, pj)ï¼å
¶ä¸djæ¯ä»èµ·æºç¹så°ç¹jçæçè·¯å¾çé¿åº¦ (ä»é¡¶ç¹å°å
¶æ¬èº«çæçè·¯å¾æ¯é¶è·¯(没æ弧çè·¯)ï¼å
¶é¿åº¦çäºé¶)ï¼pjåæ¯ä»så°jçæçè·¯å¾ä¸jç¹çåä¸ç¹ãæ±è§£ä»èµ·æºç¹så°ç¹jçæçè·¯å¾ç®æ³çåºæ¬è¿ç¨å¦ä¸ï¼
ãã1) åå§åãèµ·æºç¹è®¾ç½®ä¸ºï¼â ds=0, ps为空;â¡ ææå
¶ä»ç¹: di=â, pi=?;⢠æ è®°èµ·æºç¹sï¼è®°k=s,å
¶ä»ææç¹è®¾ä¸ºæªæ è®°çã
ãã2) æ£éªä»ææå·²æ è®°çç¹kå°å
¶ç´æ¥è¿æ¥çæªæ è®°çç¹jçè·ç¦»ï¼å¹¶è®¾ç½®ï¼
dj=minï¼»dj, dk+lkjï¼½
å¼ä¸ï¼lkjæ¯ä»ç¹kå°jçç´æ¥è¿æ¥è·ç¦»ã
ãã3) éåä¸ä¸ä¸ªç¹ãä»æææªæ è®°çç»ç¹ä¸ï¼éådj ä¸æå°çä¸ä¸ªiï¼
di=minï¼»dj, æææªæ è®°çç¹jï¼½
ç¹i就被é为æçè·¯å¾ä¸çä¸ç¹ï¼å¹¶è®¾ä¸ºå·²æ è®°çã
ãã4) æ¾å°ç¹içåä¸ç¹ãä»å·²æ è®°çç¹ä¸æ¾å°ç´æ¥è¿æ¥å°ç¹içç¹j*ï¼ä½ä¸ºåä¸ç¹,设置ï¼
i=j*
ãã5) æ è®°ç¹iãå¦æææç¹å·²æ è®°ï¼åç®æ³å®å
¨æ¨åºï¼å¦åï¼è®°k=iï¼è½¬å°2) å继ç»ã
#include <stdio.h>
#define true 1
#define false 0
#define I 9999 /* æ 穷大 */
#define N 20 /* åå¸é¡¶ç¹çæ°ç® */
int cost[N][N] = {
{0,3,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I,I,I},
{3,0,5,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I,I,I},
{I,5,0,4,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I},
{I,I,4,0,2,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I},
{I,I,I,2,0,I,I,I,I,7,I,I,I,I,I,I,I,I,I,I},
{1,I,I,I,I,0,1,I,I,I,2,I,I,I,I,I,I,I,I,I},
{I,6,I,I,I,1,0,6,I,I,I,7,I,I,I,I,I,I,I,I},
{I,I,1,I,I,I,6,0,2,I,I,I,3,I,I,I,I,I,I,I},
{I,I,I,6,I,I,I,2,0,8,I,I,I,4,I,I,I,I,I,I},
{I,I,I,I,7,I,I,I,8,0,I,I,I,I,5,I,I,I,I,I},
{I,I,I,I,I,2,I,I,I,I,0,4,I,I,I,3,I,I,I,I},
{I,I,I,I,I,I,7,I,I,I,4,0,3,I,I,I,4,I,I,I},
{I,I,I,I,I,I,I,3,I,I,I,3,0,3,I,I,I,5,I,I},
{I,I,I,I,I,I,I,I,4,I,I,I,3,0,7,I,I,I,2,I},
{I,I,I,I,I,I,I,I,I,5,I,I,I,7,0,I,I,I,I,3},
{I,I,I,I,I,I,I,I,I,I,3,I,I,I,I,0,5,I,I,I},
{I,I,I,I,I,I,I,I,I,I,I,4,I,I,I,5,0,8,I,I},
{I,I,I,I,I,I,I,I,I,I,I,I,5,I,I,I,8,0,6,I},
{I,I,I,I,I,I,I,I,I,I,I,I,I,2,I,I,I,6,0,4},
{I,I,I,I,I,I,I,I,I,I,I,I,I,I,3,I,I,I,4,0}
};
int dist[N]; /* åå¨å½åæçè·¯å¾é¿åº¦ */
int v0 = 'A' - 65; /* åå§ç¹æ¯ A */
void main()
{
int final[N], i, v, w, min;
/* åå§åæçè·¯å¾é¿åº¦æ°æ®ï¼æææ°æ®é½ä¸æ¯æç»æ°æ® */
for (v = 0; v < N; v++) {
final[v] = false;
dist[v] = cost[v0][v];
}
/* é¦å
év0å°v0çè·ç¦»ä¸å®æçï¼æç»æ°æ® */
final[v0] = true;
/* 寻æ¾å¦å¤ N-1 个ç»ç¹ */
for (i = 0; i < N-1; i++) {
min = I; /* åå§æçé¿åº¦æ 穷大 */
/* 寻æ¾æççè¾¹ */
for (w = 0; w < N; w++) {
if (!final[w] && dist[w] < min) {
min = dist[w];
v = w;
}
}
final[v] = true; /* å å
¥æ°è¾¹ */
for (w = 0; w < N; w++) { /* æ´æ° dist[] æ°æ® */
if (!final[w] && dist[v] + cost[v][w] < dist[w]) {
dist[w] = dist[v] + cost[v][w];
}
}
}
for (i = 0; i < N; i++) { /* æ¾ç¤ºå°çè§å¨ */
printf("%c->%c: %2d\t", v0 + 65, i + 65, dist[i]);
}
}
温馨提示:答案为网友推荐,仅供参考