中科创达实训第七天：Python包和文件读写

一、课件

二、课后题

三、题目答案

只适合本题目答案：

# 地图信息
mapDoc = []
# 路径信息
road = []
road2 = []


# 加载地图信息
def mapData():
    # 加载地图信息
    map = open("map.txt")
    # 地图数据
    mapData = map.readlines()
    # 遍历地图信息
    for item in mapData:
        tempArr = {
            'air': int(item[1]),
            'air2': int(item[3]),
            "km": int(item.split(",")[-1].split(")")[0])
        }
        mapDoc.append(tempArr)
    map.close()


# 另一个机场
def another(dic, mainOne):
    if dic['air'] == mainOne:
        return int(dic['air2'])
    elif dic['air2'] == mainOne:
        return int(dic['air'])


# 主计算函数
def cala_short_path(start, end):
    # 执行加载地图函数
    mapData()

    if start == end or start > 10 > 0 or end > 10 > 0:
        print("输入错误")
        return

    # 先直接判断一遍
    def first(sideOne, mapDoc):
        for itemAir in mapDoc:
            if itemAir['air'] == sideOne or itemAir['air2'] == sideOne:
                tempSideOne = another(itemAir, sideOne)  # 新的sideOne
                if tempSideOne == end:
                    road.append(tempSideOne)
                    return int(itemAir['km'])

    # 递归+函数
    def reKm(sideOne, mapDoc):
        for item in mapDoc:
            # 没有符合要求跳过
            if sideOne != item['air'] and sideOne != item['air2']:
                continue
            sideOne = another(item, sideOne)  # 新的sideOne
            # 等于end 结束
            if sideOne == end:
                road.append(end)
                return int(item['km'])
            else:
                road.append(sideOne)
                mapDoc.remove(item)
                return reKm(sideOne, mapDoc) + item['km']

    # -遍历
    def reKm2(sideOne, mapDoc):
        for item in mapDoc:
            if sideOne != item['air'] and sideOne != item['air2']:
                continue
            sideOne = another(item, sideOne)  # 新的sideOne
            if sideOne == end:
                road2.append(end)
                return int(item['km'])
            else:
                road2.append(sideOne)
                mapDoc.remove(item)
                return reKm2(sideOne, mapDoc) + item['km']

    # 格式化打印
    def print_route(km, route):
        temp_route = ''
        for item in route:
            temp_route += '%s-' % (item)
        temp_route = temp_route[0: len(temp_route) - 1]
        temp_route += ','
        temp_route += str(km) + 'Km'
        print(temp_route)

    if first(start, mapDoc) == None:
        road.clear()
        road.append(start)
        # 执行函数
        totalKM = reKm(start, mapDoc)

        # 重新加载地图
        mapData()
        road2.clear()
        road2.append(start)
        # 执行函数
        totalKM2 = reKm2(start, mapDoc)
        if totalKM > totalKM2:
            totalKM = totalKM2
        if len(road) > len(road2):
            rodeTime = road2
        else:
            rodeTime = road
        print_route(totalKM, rodeTime)
        # return totalKM, rodeTime
    else:
        road.clear()
        road.append(start)
        rodeTime = road
        print_route(first(start, mapDoc), rodeTime)
        # return first(start, mapDoc), rodeTime



cala_short_path(4, 2)
cala_short_path(3, 1)
cala_short_path(5, 4)
cala_short_path(1, 4)
cala_short_path(4, 1)
cala_short_path(-1, 40)

多位置最短距离答案：

# 函数：Dijkstra算法
import numpy as np

# 常量
INF = 9999  # 定义不可达距离
MAP_PATH = 'map.txt'

# 加载map信息
def mapData():
    # 加载地图信息
    map = open(MAP_PATH)
    # 地图数据
    mapData = map.readlines()
    # 机场数量
    count = len(mapData)
    # 遍历地图信息
    graph = np.zeros([count, count],int)
    for line in range(count):
        for one in range(count):
            graph[line - 1][one - 1] = INF
    for item in mapData:
        col = int(item[1]) - 1
        row = int(item[3]) - 1
        graph[col][row] = int(item.split(",")[-1].split(")")[0])

        row = int(item[1]) - 1
        col = int(item[3]) - 1
        graph[col][row] = int(item.split(",")[-1].split(")")[0])
    map.close()
    return graph


# 算法
def calc_short_path(start, end):
    graph = mapData()
    if  start > 10 or start < 0 or end < 0 or end > 10:
        print("输入有误")
        return
    start -= 1
    end -= 1
    points = len(graph)
    pre = [0] * (points)  # 记录前驱
    vis = [0] * (points)  # 记录节点遍历状态
    dis = [INF for i in range(points)]  # 保存最短距离
    road = [0] * (points)  # 保存最短路径
    roads = []

    # 初始化起点到其他点的距离
    for i in range(points):
        if i == start:
            dis[i] = 0
        else:
            dis[i] = graph[start][i]
        if graph[start][i] != INF:
            pre[i] = start
        else:
            pre[i] = -1
    vis[start] = 1

    # 每次循环确定一条最短路
    for i in range(points):
        minimum = INF
        # 确定当前最短路
        for j in range(points):
            if vis[j] == 0 and dis[j] < minimum:
                t = j
                minimum = dis[j]
                # 找到并标记最短的一条路径
        vis[t] = 1
        for j in range(points):
            if vis[j] == 0 and dis[j] > dis[t] + graph[t][j]:
                dis[j] = dis[t] + graph[t][j]
                pre[j] = t
    p = end
    length = 0
    while p >= 0 and length < points:
        road[length] = p + 1  # 这里做了修改
        p = pre[p]
        length += 1
    length -= 1
    while length >= 0:
        roads.append(road[length])
        length -= 1
    # 输出最短路结果
    print_route(dis[end], roads)
    return dis[end], roads


# 格式化打印
def print_route(km, route):
    temp_route = ''
    for item in route:
        temp_route += '%s-' % (item)
    temp_route = temp_route[0: len(temp_route) - 1]
    temp_route += ','
    temp_route += str(km) + 'Km'
    print(temp_route)


# 测试用例
calc_short_path(3, 5)
calc_short_path(1, 5)
calc_short_path(2, 5)
calc_short_path(2, 3)
calc_short_path(7, 2)
calc_short_path(2, 66)