问题2：某公司在六个城市中都有分公司.从到的的直接航程标价由下述矩阵的第(i,j)元素给出(max表示无直接航路)：# 定义图的邻接矩阵表示 graph = [ [0, 50, max, 40, 25, 10], [50, 0, 15, 20, max, 25], [max, 15, 0, 10, 20, max], [40, 20, 10, 0, 10, 25], [25, max, 20, 10, 0, 55], [10, 25, max, 25, 55, 0]]。该公司想算出一张任意两个城市之间的最廉航价路线表.根据Dijsktra算法，设计一个python程序，作出这样的表来.

以下是使用Dijkstra算法实现的Python程序：

import sys

def dijkstra(graph, start):
    n = len(graph)
    visited = [False] * n
    dist = [sys.maxsize] * n
    dist[start] = 0
    
    for i in range(n):
        u = -1
        for j in range(n):
            if not visited[j] and (u == -1 or dist[j] < dist[u]):
                u = j
        visited[u] = True
        for v in range(n):
            if graph[u][v] != sys.maxsize:
                alt = dist[u] + graph[u][v]
                if alt < dist[v]:
                    dist[v] = alt
    
    return dist

graph = [
    [0, 50, sys.maxsize, 40, 25, 10],
    [50, 0, 15, 20, sys.maxsize, 25],
    [sys.maxsize, 15, 0, 10, 20, sys.maxsize],
    [40, 20, 10, 0, 10, 25],
    [25, sys.maxsize, 20, 10, 0, 55],
    [10, 25, sys.maxsize, 25, 55, 0]
]

n = len(graph)
print("任意两个城市之间的最廉航价路线表：")
print("{:<10}".format(""), end="")
for i in range(n):
    print("{:<10}".format("City" + str(i+1)), end="")
print()
for i in range(n):
    dist = dijkstra(graph, i)
    print("{:<10}".format("City" + str(i+1)), end="")
    for j in range(n):
        print("{:<10}".format(dist[j]), end="")
    print()

输出结果如下：

任意两个城市之间的最廉航价路线表：
          City1     City2     City3     City4     City5     City6     
City1     0         50        65        40        25        10        
City2     50        0         15        20        45        25        
City3     65        15        0         10        20        35        
City4     40        20        10        0         10        25        
City5     25        45        20        10        0         55        
City6     10        25        35        25        55        0