西电软院算法上机3代码

西电软院算法上机3的原题以及python代码实现

#!/usr/bin/python
# coding=utf-8
INF = float（“inf“）

def printSolution（distGraph）:
    string = “inf“
    nodes = distGraph.keys（）
    for n in nodes:
        print “\t%6s“%（n）
    print “ “
    for i in nodes:
        print“%s“%（i）
        for j in nodes:
            if distGraph[i][j] == INF:
                print “%10s“%（string）
            else:
                print “%10s“%（distGraph[i][j]）
        print “ “

def floydWarshall（graph）:
    nodes = graph.keys（）
    distance = {}
    for n in nodes:
        distance[n] = {}
        for k in nodes:
            distance[n][k] = graph[n][k]
    for k in nodes:
        for i in nodes:
            for j in nodes:
                if distance[i][k] + distance[k][j] < distance[i][j]:
                    distance[i][j] = distance[i][k]+distan

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2016-05-09 23:25  3\
     文件         162  2016-05-09 23:17  3\.~actice 3.doc
     文件        1202  2016-05-09 18:00  3\floyd_sortest.py
     文件        3262  2016-05-09 23:05  3\knapsack.py
     文件         745  2016-05-09 01:55  3\ms_shortest.py
     文件         315  2016-05-09 23:13  3\scheduling.py
     文件        1289  2016-05-09 17:56  3\ss_shortest.py