def?PRINT_GRAPH_MATRIX（G）:
????format_str?=?“%-8.2f“?*?len（G）
????for?row?in?G:
????????print（format_str?%?tuple（row））

def?CREATE_GRAPH_MATRIX（n?val?=?None）:
????g?=?[[val?for?i?in?range（n）]?for?j?in?range（n）]
????return?g

def?COPY_GRAPH_MATRIX（G）:
????n?=?len（G）
????g?=?CREATE_GRAPH_MATRIX（n）
????for?i?in?range（n）:
????????for?j?in?range（n）:
????????????g[i][j]?=?G[i][j]
????return?g

def?GRAPH_CONNECT（G?i?j?weight）:
????G[i-1][j-1]?=?weight

def?EXTEND_SHORTEST_PATHS（L?W）:
????n?=?len（L）
????rL?=?CREATE_GRAPH_MATRIX（n?float（“inf“））
????for?i?in?range（n）:
????????for?j?in?range（n）:
????????????for?k?in?range（n）:
????????????????#print（i?j?k?rL[i][j]?L[i][k]?W[k][j]）
????????????????rL[i][j]?=?min（rL[i][j]?L[i][k]?+?W[k][j]）
????????????????#print（rL[i][j]）
????????????#print（“-------------“）
????return?rL

def?SLOW_ALL_PAIRS_SHORTEST_PATHS（W）:
????n?=?len（W）
????L?=?COPY_GRAPH_MATRIX（W）
????for?m?in?range（1?n）:
????????L?=?EXTEND_SHORTEST_PATHS（L?W）
????????#PRINT_GRAPH_MATRIX（L）
????????#print（“=================“）
????return?L

def?FASTER_ALL_PAIRS_SHORTEST_PATHS（W）:
????n?=?len（W）
????L?=?COPY_GRAPH_MATRIX（W）
????m?=?1
????while?m?????????L?=?EXTEND_SHORTEST_PATHS（L?L）
????????m?=?2*m
????return?L


if?__name__?==?“__main__“:
????G?=?CREATE_GRAPH_MATRIX（5?float（“inf“））
????GRAPH_CONNECT（G?1?1?0）
????GRAPH_CONNECT（G?2?2?0）
????GRAPH_CONNECT（G?3?3?0）
????GRAPH_CONNECT（G?4?4?0）
????GRAPH_CONNECT（G?5?5?0）
????GRAPH_CONNECT（G?1?2?3）
????GRAPH_CONNECT（G?1?3?8）
????GRAPH_CONNECT（G?1?5?-4）
????GRAPH_CONNECT（G?2?4?1）
????GRAPH_CONNECT（G?2?5?7）
????GRAPH_CONNECT（G?3?2?4）
????GRAPH_CONNECT（G?4?1?2）
????GRAPH_CONNECT（G?4?3?-5）
????GRAPH_CONNECT（G?5?4?6）

????PRINT_GRAPH_MATRIX（G）
????print（“====================“）
????L1?=?SLOW_ALL_PAIRS_SHORTEST_PATHS（G）
????PRINT_GRAPH_MATRIX（L1）
????print（“====================“）
????L2?=?FASTER_ALL_PAIRS_SHORTEST_PATHS（G）
????PRINT_GRAPH_MATRIX（L2）

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????2066??2017-04-19?20:14??chapter25\25.1.py

?????文件???????2209??2017-04-19?20:27??chapter25\25.1_1.py

?????文件????????548??2017-04-19?20:40??chapter25\25.1_2-5.py

?????文件???????2560??2017-04-20?14:47??chapter25\25.1_6.py

?????文件???????3388??2017-04-20?21:27??chapter25\25.1_7-10.py

?????文件???????2438??2017-04-24?21:15??chapter25\25.2.py

?????文件???????2103??2017-04-24?20:17??chapter25\25.2_1.py

?????文件????????679??2017-04-24?17:24??chapter25\25.2_2-6.py

?????文件???????2626??2017-04-24?21:43??chapter25\25.2_7.py

?????文件????????794??2017-04-25?10:45??chapter25\25.2_8-9.py

?????文件???????5557??2017-04-25?17:21??chapter25\25.3.py

?????文件???????5623??2017-04-25?18:10??chapter25\25.3_1.py

?????文件???????1379??2017-04-25?21:20??chapter25\25.3_2-6.py

?????文件???????2474??2017-04-26?16:53??chapter25\25_1.py

?????文件????????872??2017-04-26?17:41??chapter25\25_2.py

?????目錄??????????0??2017-04-26?16:53??chapter25

-----------?---------??----------?-----??----

????????????????35316????????????????????16