python实现有向图单源最短路径迪杰斯特拉 算法

用python实现迪杰斯特拉算法，单源最短路径，有向图权值无负值，用邻接矩阵来存储有向图，实现路径存储和路径打印

‘‘‘
inf：表示正无穷，初始化不与定点相连的节点的距离
visited[ver_num]：表示是否已经经历过该节点
ver_num：当前节点下标
cost[u][v]:表示u和v之间路径的长度
list表示邻接矩阵
path表示当前节点的前驱节点
distance表示当前最短路径
‘‘‘
# 测试用例
‘‘‘
        武大    地大    图书城  光谷    华科
武大      0      6       24     11      inf
地大     inf     0       inf    4       8
图书城   inf     inf     0      11      inf 
光谷     inf     5       9      0       7
华科     inf     inf     inf    5       inf
‘‘‘

list = [
    [062411float（“inf“）]
    [float（“inf“）0float（“inf“）48]
    [float（“inf“）float（“inf“）011float（“inf“）]
    [float（“inf“）5907]
    [float（“inf“）float（“inf“）float（“inf“）5float（“inf“）]
]

dicts = {
    ‘0‘:‘武大‘
    ‘1‘:‘地大‘
    ‘2‘:‘图书城‘
    ‘3‘:‘光谷‘
    ‘4‘:‘华科‘
}

# 测试5个节点
ver_num = 5

# 将每一个节点都标记为False
visited = [False for _ in range（ver_num）]

# 将所有的节点间距离声明为inf
cost = [[float（‘inf‘） for _ in range（ver_num）] for _ in range（ver_num）]

# 定义一个存放路径的下标列表，即当前节点的前驱节点
path = []

# 定义列表存放最短路径长度
distance = []

def main（）:

    # 将节点间权重值初始化
    init_matrix（costlist）
    # 打印当前邻接矩阵
    print_matrix（cost）
    # 初始化最短路径distance
    init_distance（distancecost）
    # 初始化路径列表path
    init_path（pathcost）
    # 进行算法主体部分从0点开始
    dijkstra（0costpathdistancevisited）
    # 选择路径 从武汉到其他四个地方
    choose_place（dicts）

# 打印当前存有权值的矩阵
def print_matrix（cost）:
    # print（cost）   用于测试
    for _ in cost:
        for row in range（len（_））:
            print（_[row]end = “\t“）
        print（“\n“）


# 初始化邻接矩阵
def init_matrix（costlist）:
    for _ in range（ver_num）:
        cost[_] = list[_][:]


def init_distance（distancecost）:
    # 暂时用0作为源点
    # print（cost[0]）
    for i in range（5）:
        distance.append（cost[0][i]）
        print（distance[i]）

def init_path（pathcost）:
    # 针对源点，将是否与源点之间有边进行初始化
    # 有边则进行记录其前驱节点为0，无边则记录其其前驱为-1
    path.append（-1）
    for i in range（1len（cost[0]））:
        if cost[0][i] == float（“inf“）:
            path.append（-1）
        else:
            path.append（0）
    print（path）


# 进行迪杰斯特拉算法 以0节点为标准
def dijkstra（scostpathdistancevisited）:
    # 标记已经访问
    visited[s] = True
    
    while True:
        ver = -1
        # 寻找当前未被标记的最小边对应的节点
        ver_min = float（“inf“）
        for u in range（ver_num）:
            if visited[u] == False and distance[u] < ver_min:
                ver_min = distance[u]
                ver = u
        # 测试每次选择的节点
        # print（ver）

        # while循环结束条件
        if False not in visited:
            break

        visited[ver] = True

        # 更新当前最短路径
        for v in range（ver_num）:
            # distance[v] = min（distance[v]distance[ver] + cost[ver][v]）
            
            if distance[v] > distance[ver] + cost[ver][v]:
                distance[v] = distance[ver] + cost[ver][v]
                # 更新path
                path[v] = ver
            # print（distance[v]）
            # 暂时没有更新path
    # print（distance）
    # print（path）

# 选择目的

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        4512  2020-09-27 20:37  算法\major_dijkstra.py
     目录           0  2020-09-27 20:58  算法\