我有一个带有正边权的有向无环图.它有一个源和一组目标(距离源最远的顶点).我找到了从源到每个目标的最短路径.其中一些路径重叠.我想要的是一个最短路径树,它最小化所有边缘的权重总和.
例如,考虑两个目标.给定所有边缘权重相等,如果它们在其大部分长度上共享单个最短路径,那么这优于两个大多数非重叠的最短路径(树中较少的边缘等于较低的总成本).
另一个例子:两条路径长度的一小部分不重叠,非重叠路径的成本高,但长共享路径的成本低(组合成本低).另一方面,两条路径在其大部分长度上不重叠,非重叠路径的成本低,但短共享路径的成本高(同样,组合成本低).有很多种组合.考虑到从源到目标的所有最短路径,我想找到总体成本最低的解决方案.
换句话说,我想要最短,最短的路径树.
这会和任何人敲响吗？有人能指出我相关的算法或类似的应用程序吗？
干杯!