8.6 恷玉揃抄!耽匯斤競泣岻寂議恷玉揃抄
盾畳宸倖諒籾議匯倖一隈頁?耽肝參匯倖競泣葎坿泣?嶷鹸孃棋杵旬帽蒙性麻隈肝。宸劔?宴辛箔誼耽匯潤競泣議恷玉揃抄。悳議峇佩扮寂葎O(n3)。
宸戦勣初府喇献代卅蟻(Floyd)戻竃議総匯倖麻隈。宸倖麻隈議扮寂鹸墫業匆頁O(n3),徽侘塀貧酒汽乂。
献代卅蟻麻隈挽貫夕議揮幡惣俊裳專cost 竃窟?凪児云房?頁?
邪譜箔貫競泣vi 欺vj 議恷玉揃抄。泌惚貫vi 欺vi 嗤察?夸貫vi 欺vj 贋壓匯訳海業葎edges[i][j]議揃抄?乎揃抄音匯協頁恷玉揃抄?賓俶序佩n 肝編冥。遍枠深打揃抄?vi, v0,vj?頁倦贋壓?軸登艶察?vi, v0?才(v0, vj)頁倦贋壓?。泌惚贋壓?夸曳熟?vi, vj?才?vi,v0, vj?議揃抄海業函海業熟玉宀葎貫vi 欺vj 議嶄寂競泣議會催音寄噐0 議恷玉揃抄。邪泌壓揃抄貧壅奐紗匯倖競泣v1?匆祥頁傍?泌惚?vi, …, v1?才?v1, …, vj?蛍艶頁輝念孀欺議嶄寂競泣議會催音寄噐0 議恷玉揃抄?椎担?vi, …, v1, … , vj? 祥嗤辛嬬頁貫vi 欺vj 議嶄寂競泣議會催音寄噐1 議恷玉揃抄。繍万才厮将誼欺議貫vi 欺vj 嶄寂競泣會催音寄噐0 議恷玉揃抄屢曳熟?貫嶄僉竃嶄寂競泣議會催音寄噐1 議恷玉揃抄岻朔?壅奐紗匯倖競泣v2?写偬序佩編冥。卆肝窃容。壓匯違秤趨和?飛?vi, …, vk?才?vk, …, vj?
蛍艶頁貫vi 欺vk 才貫vk 欺vj 議嶄寂競泣議會催音寄噐k-1 議恷玉揃抄?夸繍?vi, …,vk, …, vj?才厮将誼欺議貫vi 欺vj 拝嶄寂競泣會催音寄噐k-1 議恷玉揃抄屢曳熟?凪海業熟玉宀宴頁貫vi 欺vj 議嶄寂競泣議會催音寄噐k 議恷玉揃抄。宸劔?壓将狛n 肝曳熟朔?恷朔箔誼議駅頁貫vi 欺vj 議恷玉揃抄。
梓緩圭隈?辛參揖扮箔誼光斤競泣寂議恷玉揃抄。
孖協吶匯倖n 竣圭專會双。
貫貧峰柴麻巷塀辛需?D(1)[i][j]頁貫vi 欺vj 議嶄寂競泣議會催音寄噐1 議恷玉揃抄議海業?D( k)[i][j] 頁貫vi 欺vj 議嶄寂競泣議倖方音寄噐k 議恷玉揃抄議海業?D( n-1)[i][j] 祥頁貫vi 欺vj 議恷玉揃抄議海業。
喇緩誼欺箔販吭曾競泣寂議恷玉揃抄議麻隈8.18。
void ShortestPath_2 (Mgraph G, PathMatrix *P[],DistancMatrix *D)
{/*喘Floyd 麻隈箔嗤?利G 嶄光斤競泣v 才w 岻寂議恷玉揃抄P[v][w]式凪揮幡海業D[v][w]。*/
/*飛P[v][w][u]葎TRUE?夸u 頁貫v 欺w 輝念箔誼議恷玉揃抄貧議競泣。*/
for(v=0;v<G.vexnum;++v) /*光斤競泣岻寂兜兵厮岑揃抄式鉦宣*/
for(w=0;w<G,vexnum;++w)
{ D[v][w]=G.arcs[v][w];
for(u=0;u<G,vexnum;++u) P[v][w][u]=FALSE;
if (D[v][w]<INFINITY) /*貫v 欺w 嗤岷俊揃抄*/
{ P[v][w][v]=TRUE;
}
}
for(u=0; u<G.vexnum; ++u)
for(v=0; v<G.vexnum; ++v)
for(w=0;w<G.vexnum;++w)
if (D[v][u]+D[u][w]<D[v][w]) /*貫v 将u 欺w 議匯訳揃抄厚玉*/
{D[v][w]=D[v][u]+D[u][w];
for(i=0;i<G.vexnum;++i)
P[v][w][i]=P[v][u][i]||P[u][w][i];
}
}/* ShortestPath_2*/
麻隈8.18
夕8.28 公竃阻匯倖酒汽議嗤?利式凪惣俊裳專。夕8.29 公竃阻喘Floyd 麻隈箔乎嗤?利嶄耽斤競泣岻寂議恷玉揃抄狛殻嶄?方怏D 才方怏P 議延晒秤趨。
宸戦勣初府喇献代卅蟻(Floyd)戻竃議総匯倖麻隈。宸倖麻隈議扮寂鹸墫業匆頁O(n3),徽侘塀貧酒汽乂。
献代卅蟻麻隈挽貫夕議揮幡惣俊裳專cost 竃窟?凪児云房?頁?
邪譜箔貫競泣vi 欺vj 議恷玉揃抄。泌惚貫vi 欺vi 嗤察?夸貫vi 欺vj 贋壓匯訳海業葎edges[i][j]議揃抄?乎揃抄音匯協頁恷玉揃抄?賓俶序佩n 肝編冥。遍枠深打揃抄?vi, v0,vj?頁倦贋壓?軸登艶察?vi, v0?才(v0, vj)頁倦贋壓?。泌惚贋壓?夸曳熟?vi, vj?才?vi,v0, vj?議揃抄海業函海業熟玉宀葎貫vi 欺vj 議嶄寂競泣議會催音寄噐0 議恷玉揃抄。邪泌壓揃抄貧壅奐紗匯倖競泣v1?匆祥頁傍?泌惚?vi, …, v1?才?v1, …, vj?蛍艶頁輝念孀欺議嶄寂競泣議會催音寄噐0 議恷玉揃抄?椎担?vi, …, v1, … , vj? 祥嗤辛嬬頁貫vi 欺vj 議嶄寂競泣議會催音寄噐1 議恷玉揃抄。繍万才厮将誼欺議貫vi 欺vj 嶄寂競泣會催音寄噐0 議恷玉揃抄屢曳熟?貫嶄僉竃嶄寂競泣議會催音寄噐1 議恷玉揃抄岻朔?壅奐紗匯倖競泣v2?写偬序佩編冥。卆肝窃容。壓匯違秤趨和?飛?vi, …, vk?才?vk, …, vj?
蛍艶頁貫vi 欺vk 才貫vk 欺vj 議嶄寂競泣議會催音寄噐k-1 議恷玉揃抄?夸繍?vi, …,vk, …, vj?才厮将誼欺議貫vi 欺vj 拝嶄寂競泣會催音寄噐k-1 議恷玉揃抄屢曳熟?凪海業熟玉宀宴頁貫vi 欺vj 議嶄寂競泣議會催音寄噐k 議恷玉揃抄。宸劔?壓将狛n 肝曳熟朔?恷朔箔誼議駅頁貫vi 欺vj 議恷玉揃抄。
梓緩圭隈?辛參揖扮箔誼光斤競泣寂議恷玉揃抄。
孖協吶匯倖n 竣圭專會双。
D(-1)?D(0)?D(1)?…?D(k)?D(n-1)
凪嶄
D(-1)[i][j]=edges[i][j]
D( k)[i][j]=Min{D( k-1)[i][j], D( k-1)[i][k]+D( k-1)[k][j]} 0?Qk?Qn-1
D( k)[i][j]=Min{D( k-1)[i][j], D( k-1)[i][k]+D( k-1)[k][j]} 0?Qk?Qn-1
貫貧峰柴麻巷塀辛需?D(1)[i][j]頁貫vi 欺vj 議嶄寂競泣議會催音寄噐1 議恷玉揃抄議海業?D( k)[i][j] 頁貫vi 欺vj 議嶄寂競泣議倖方音寄噐k 議恷玉揃抄議海業?D( n-1)[i][j] 祥頁貫vi 欺vj 議恷玉揃抄議海業。
喇緩誼欺箔販吭曾競泣寂議恷玉揃抄議麻隈8.18。
void ShortestPath_2 (Mgraph G, PathMatrix *P[],DistancMatrix *D)
{/*喘Floyd 麻隈箔嗤?利G 嶄光斤競泣v 才w 岻寂議恷玉揃抄P[v][w]式凪揮幡海業D[v][w]。*/
/*飛P[v][w][u]葎TRUE?夸u 頁貫v 欺w 輝念箔誼議恷玉揃抄貧議競泣。*/
for(v=0;v<G.vexnum;++v) /*光斤競泣岻寂兜兵厮岑揃抄式鉦宣*/
for(w=0;w<G,vexnum;++w)
{ D[v][w]=G.arcs[v][w];
for(u=0;u<G,vexnum;++u) P[v][w][u]=FALSE;
if (D[v][w]<INFINITY) /*貫v 欺w 嗤岷俊揃抄*/
{ P[v][w][v]=TRUE;
}
}
for(u=0; u<G.vexnum; ++u)
for(v=0; v<G.vexnum; ++v)
for(w=0;w<G.vexnum;++w)
if (D[v][u]+D[u][w]<D[v][w]) /*貫v 将u 欺w 議匯訳揃抄厚玉*/
{D[v][w]=D[v][u]+D[u][w];
for(i=0;i<G.vexnum;++i)
P[v][w][i]=P[v][u][i]||P[u][w][i];
}
}/* ShortestPath_2*/
麻隈8.18
夕8.28 公竃阻匯倖酒汽議嗤?利式凪惣俊裳專。夕8.29 公竃阻喘Floyd 麻隈箔乎嗤?利嶄耽斤競泣岻寂議恷玉揃抄狛殻嶄?方怏D 才方怏P 議延晒秤趨。