算法导论第二十五章习题解答

能用代码表示的都用代码表示，不能表示的写出思路，思路都没写的就是我也做不出来。

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 < n:
        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