Bellman-Ford算法

Bellman-Ford是一种容易理解的单源最短路径算法, Bellman-Ford算法需要两个数组进行辅助:

dis[i]: 存储顶点i到源点已知最短路径
path[i]: 存储顶点i到源点已知最短路径上, i的前一个顶点.

若图有n个顶点, 则图中最长简单路径长度不超过n-1, 因此Ford算法进行n-1次迭代确保获得最短路径.

Ford算法的每次迭代遍历所有边, 并对边进行松弛(relax)操作. 对边e进行松弛是指: 若从源点通过e.start到达e.stop的路径长小于已知最短路径, 则更新已知最短路径.

为了便于描述, 本文采用python实现算法. 首先实现两个工具函数:

INF = 1e6

def make_mat(m, n, fill=None):

    mat = []

    for i in range(m):

        mat.append([fill] * n)

    return mat

def get_edges(graph):

    n = len(graph)

    edges = []

    for i in range(n):

        for j in range(n):

            if graph[i][j] != 0:

                edges.append((i, j, graph[i][j]))

    return edges

make_mat用于初始化二维数组, get_edges用于将图由邻接矩阵表示变换为边的列表.

接下来就可以实现Bellman-Ford算法了:

def ford(graph, v0):

    n = len(graph)

    edges = get_edges(graph)

    dis = [INF] * n

    dis[v0] = 0

    path = [0] * n

    for k in range(n-1):

        for edge in edges:

            # relax

            if dis[edge[0]] + edge[2] < dis[edge[1]]:

                dis[edge[1]] = dis[edge[0]] + edge[2]

                path[edge[1]] = edge[0]

   return dis, path

初始化后执行迭代和松弛操作, 非常简单.

由path[i]获得最短路径的前驱顶点, 逐次迭代得到从顶点i到源点的最短路径. 倒序即可得源点到i的最短路径.

def show(path, start, stop):

    i = stop

    tmp = [stop]

    while i != start:

        i = path[i]

        tmp.append(i)

    return list(reversed(tmp))

Ford算法允许路径的权值为负, 但是若路径中存在总权值为负的环的话, 每次经过该环最短路径长就会减少. 因此, 图中的部分点不存在最短路径(最短路径长为负无穷).

若路径中不存在负环, 则进行n-1次迭代后不存在可以进行松弛的边. 因此再遍历一次边, 若存在可松弛的边说明图中存在负环.

这样改进得到可以检测负环的Ford算法:

def ford(graph, v0):

    n = len(graph)

    edges = get_edges(graph)

    dis = [INF] * n

    dis[v0] = 0

    path = [0] * n

    for k in range(n-1):

        for edge in edges:

            # relax

            if dis[edge[0]] + edge[2] < dis[edge[1]]:

                dis[edge[1]] = dis[edge[0]] + edge[2]

                path[edge[1]] = edge[0]

    # check negative loop

    flag = False

    for edge in edges:

        # try to relax

        if dis[edge[0]] + edge[2] < dis[edge[1]]:

            flag = True

            break

    if flag:

        return False

    return dis, path

完整python代码

Dijkstra算法

Dijkstra算法是一种贪心算法, 但可以保证求得全局最优解. Dijkstra算法需要和Ford算法同样的两个辅助数组:

dis[i]: 存储顶点i到源点已知最短路径
path[i]: 存储顶点i到源点已知最短路径上, i的前一个顶点.

Dijkstra算法的核心仍然是松弛操作, 但是选择松弛的边的方法不同. Dijkstra算法使用一个小顶堆存储所有未被访问过的边, 然后每次选择其中最小的进行松弛.

def dijkstra(graph, v0):

    n = len(graph)

    dis = [INF] * n

    dis[v0] = 0

    path = [0] * n

    unvisited = get_edges(graph)

    heapq.heapify(unvisited)

    while len(unvisited):

        u = heapq.heappop(unvisited)[1]

        for v in range(len(graph[u])):

            w = graph[u][v]

            if dis[u] + w < dis[v]:

                dis[v] = dis[u] + w

                path[v] = u

    return dis, path

完整python代码

Floyd

floyd算法是采用动态规划思想的多源最短路径算法. 它同样需要两个辅助数组, 但作为多源最短路径算法, 其结构不同:

dis[i][j]: 保存从顶点i到顶点j的已知最短路径, 初始化为直接连接
path[i][j]: 保存从顶点i到顶点j的已知最短路径上下一个顶点, 初始化为j

def floyd(graph):

	# init

    m = len(graph)

    dis = make_mat(m, m, fill=0)

    path = make_mat(m, m, fill=0)

    for i in range(m):

        for j in range(m):

            dis[i][j] = graph[i][j]

            path[i][j] = j

    for k in range(m):

        for i in range(m):

            for j in range(m):

                # relax

                if dis[i][k] + dis[k][j] < dis[i][j]:

                    dis[i][j] = dis[i][k] + dis[k][j]

                    path[i][j] = path[i][k]

    return dis, path

算法核心是遍历顶点k, i, j. 若从顶点i经过顶点k到达顶点j的路径, 比已知从i到j的最短路径短, 则更新已知最短路径.

完整python代码

巴特西

求最短路径的三种算法: Ford, Dijkstra和Floyd

Bellman-Ford算法

Dijkstra算法

Floyd

最新文章

热门文章