DAG 的最短路径算法

求图中节点的单源最短路径可以使用Dijkstra,BellmanFord, SPFA算法，而对于有向无环图DAG来说，可以通过简单的动态规划来进行求解。
DAG的独特之处是所有节点可以线性化（拓扑序列），使得所有边保持从左到右的方向，如下图：

思路
动态规划的递推需要一个线性或者树形的顺序，对于DAG，我们可以将节点按照拓扑顺序来进行线性化，这样就可以来进行递推。
拓扑顺序中节点v排在节点u之后，则只有可能从u到达v，而不能反过来；对于当前的节点v，在拓扑序列中向前查找，可能找到一些可以到达该顶点的其他节点，然后利用 dist[v] = min{dist[u] + w[u][v] | u 可以到达v} 来进行动态规划的递推。

伪码

DagShortestPath(G, w, s){

    对节点按照拓扑顺序进行排序

    topologically sort the nodes in G

    初始化

    for each vertex v in G{

        dist[v] = INF;

        pre[v] = NULL;

    }

    dist[s] = 0;

    //根据拓扑顺序，遍历顶点v

    for each v in G, taken in topologically sorted order{

        for each edge w[u][v]{

            if (dist[v] > dist[u] + w[u][v]){

                pre[v] = dist[u] + w[u][v];

                pre[v] = u;

            }

        }

    }

}

巴特西

DAG 的最短路径算法

最新文章

热门文章