加权有向图多条最短路径算法 - Dijkstra算法与最短路径树

加权有向图多条最短路径问题是指在一个有向图中，找出从起点到终点的多条路径，使得这些路径的总权值最小。

解决这个问题可以使用Dijkstra算法和最短路径树的概念。Dijkstra算法用于计算从起点到其他所有顶点的最短路径，并且可以记录下所有的最短路径树。

具体步骤如下：

1. 初始化距离数组dist[]，将起点设置为0，其他顶点设置为无穷大。
2. 初始化最短路径树数组path[]，将起点的前驱顶点设置为-1。
3. 选取dist[]中最小的未被访问的顶点u。
4. 对u的所有邻接顶点v，如果dist[v] > dist[u] + weight(u, v)，则更新dist[v]为dist[u] + weight(u, v)，并更新path[v]为u。
5. 标记顶点u为已访问。
6. 重复步骤3-5，直到所有顶点都被访问。
7. 构建最短路径树。

根据最短路径树，可以得到从起点到终点的所有最短路径。可以通过递归遍历最短路径树，将每条路径保存下来。

需要注意的是，如果存在负权边，Dijkstra算法就不适用了，需要使用其他算法，比如Bellman-Ford算法或者Floyd-Warshall算法。

总结起来，加权有向图多条最短路径问题可以通过Dijkstra算法计算最短路径树，然后通过递归遍历最短路径树得到所有最短路径。