求第k棵树形图的算法

An Algortithm for Finding the First k Shortest Arborescences of a Digraph

本文利用拟阵交的交错序列思想，并借助改进的求第ｋ最短路的算法，给出了求第ｋ最小树形图的算法，时间复杂度为Ｏ（ｋ３｜Ａ｜３）．

This paper presents an algorithm for finding the first k shortest arborescences of a digraph G=(V,A),with vertex r as its root. It uses the properties of alternating sequences in matroids,and the algorithm for finding the first k shortest paths. The time required is at most O(k3|A|3).