Python是一种解释型、面向对象、动态数据类型的高级程序设计语言，可以用来实现Dijkstra算法和Floyd算法。Dijkstra算法是一种解决单源最短路径问题的算法，它的思想是从源点开始，每次找出离源点最近的点，从这个点出发，继续寻找离源点最近的点，直到找到终点为止。Floyd算法是一种求解任意两点之间最短路径的算法，它的思想是用动态规划的思想，从源点开始，每次求解从源点到其它点最短路径，直到求解出从源点到终点之间的最短路径为止。

Python实现Dijkstra算法

需要准备一张有向图，用邻接表存储，其中每个节点用一个链表来存储它的邻接节点，每条边用一个结构体来存储它的权重、起点和终点。定义一个数组dis，用来存储源点到其它点的距离，定义一个数组book，用来标记每个点是否已经被访问过。开始算法，从源点开始，每次找出离源点最近的点，更新dis数组，标记这个点为已经访问过，从这个点出发，继续寻找离源点最近的点，直到找到终点为止。

# 定义邻接表
graph = {
    'A': [('B', 10), ('C', 3)],
    'B': [('C', 1), ('D', 2)],
    'C': [('B', 4), ('D', 8), ('E', 2)],
    'D': [('E', 7)],
    'E': [('D', 9)]
}

# 定义距离数组
dis = {
    'A': 0,
    'B': float('inf'),
    'C': float('inf'),
    'D': float('inf'),
    'E': float('inf')
}

# 定义标记数组
book = {
    'A': False,
    'B': False,
    'C': False,
    'D': False,
    'E': False
}

# 开始算法
def dijkstra(start):
    book[start] = True
    for node in graph[start]:
        if dis[node[0]] > dis[start] + node[1]:
            dis[node[0]] = dis[start] + node[1]
    min_dis = float('inf')
    for v in dis.keys():
        if book[v] == False and dis[v] < min_dis:
            min_dis = dis[v]
            u = v
    if min_dis < float('inf'):
        dijkstra(u)

dijkstra('A')
print(dis)

Python实现Floyd算法

需要准备一张有向图，用邻接矩阵存储，其中每个节点用一个二维数组来存储它的邻接节点，每条边用一个数字来存储它的权重，如果没有边，则用一个大数字来表示。定义一个二维数组dis，用来存储源点到其它点的距离，定义一个二维数组path，用来存储最短路径。开始算法，从源点开始，每次求解从源点到其它点最短路径，直到求解出从源点到终点之间的最短路径为止。

# 定义邻接矩阵
graph = [
    [0, 5, float('inf'), 8],
    [float('inf'), 0, 2, float('inf')],
    [3, float('inf'), 0, 4],
    [float('inf'), float('inf'), 6, 0]
]

# 定义距离数组
dis = [
    [0, 5, float('inf'), 8],
    [float('inf'), 0, 2, float('inf')],
    [3, float('inf'), 0, 4],
    [float('inf'), float('inf'), 6, 0]
]

# 定义路径数组
path = [
    [-1, 0, -1, 0],
    [-1, -1, 1, -1],
    [2, -1, -1, 3],
    [-1, -1, 2, -1]
]

# 开始算法
def floyd():
    for k in range(len(dis)):
        for i in range(len(dis)):
            for j in range(len(dis)):
                if dis[i][j] > dis                
                    
本文链接：http://task.lmcjl.com/news/8102.html
                                        

                        
展开阅读全文