小编sd_*_*sd_的帖子

我正在实现一个 k 最短顶点不相交路径算法，需要一个快速算法来找到最短路径。有负权重，所以我不能使用 dijkstra，而 bellman-ford 是 O(ne)。在我最近读到的一篇论文中，作者使用所谓的 SPFA 算法在负权重图中找到最短路径，根据他们的说法，该算法的复杂度为 O(e)。听起来很有趣，但我似乎无法找到有关该算法的信息。显然这个：http ://en.cnki.com.cn/Article_en/CJFDTOTAL-XNJT402.015.htm是原始论文，但我无法访问它。

有没有人有很好的信息或者这个算法的实现？另外，是否有可用的 k 最短顶点不相交路径问题的任何来源？我找不到任何东西。

谢谢！

我有一个由(x1,y1)(x2,y2)指定的行L,并且想要计算点的坐标:

• 位于与其长度的一半处的L相交的法线上
• 是距离L一定距离D.

例子:

• 如果线是(x1,a)(x2,a)(水平),则计算点的坐标将是((x2-x1)/ 2,D).
• 如果线是(a,y1)(a,y2)(垂直),则计算点的坐标将是(D,(y2-y1)/ 2).

但我不知道如何计算所有线条的通用方式的坐标,无论角度如何(-Pi到Pi).

提前致谢!