如何使用Dijkstra算法找到由关联矩阵表示的加权有向图的最短路径？

Question

遗憾的是，在网上我只找到了邻接矩阵的Dijkstra算法，却没有找到关联矩阵的Dijkstra算法。

我的关联矩阵（第一行数字是顶点数，{}中的是边，其他都是权重；例如，权重为5的边{1;3}与顶点3关联）：

0 1 2 3 4 5 6 7

{0;1} 0 1 0 0 0 0 0 0

{0;2} 0 0 2 0 0 0 0 0

{1;2} 0 0 1 0 0 0 0 0

{1;3} 0 0 0 5 0 0 0 0

{1;4} 0 0 0 0 2 0 0 0

{2;3} 0 0 0 2 0 0 0 0

{2;4} 0 0 0 0 1 0 0 0

{2;5} 0 0 0 0 0 4 0 0

{3;4} 0 0 0 0 3 0 0 0

{3;5} 0 0 0 0 0 6 0 0

{3;6} 0 0 0 0 0 0 8 0

{4;5} 0 0 0 0 0 3 0 0

{4;6} 0 0 0 0 0 0 7 0

{5;6} 0 0 0 0 0 0 5 0

{5;7} 0 0 0 0 0 0 0 2

{6;7} 0 0 0 0 0 0 0 6

这张图：

在矩形中 - 边的权重，在圆形中只是顶点的数量，而不是权重。

我正在尝试编写一个算法，使用Dijkstra算法，将显示从键盘输入的顶点到所有其他顶点的最短路径，即路径的权重和路径本身（该路径经过的顶点）通过）应该输出。

如果你能帮我写算法，我将不胜感激=）

以防万一：我在代码中通过向量表示矩阵：

vector<vector<int>> incidenceMatrix = {
  {0,1,0,0,0,0,0,0},
  {0,0,2,0,0,0,0,0},
  {0,0,1,0,0,0,0,0},
  {0,0,0,5,0,0,0,0},
  {0,0,0,0,2,0,0,0},
  {0,0,0,2,0,0,0,0},
  {0,0,0,0,1,0,0,0},
  {0,0,0,0,0,4,0,0},
  {0,0,0,0,3,0,0,0},
  {0,0,0,0,0,6,0,0},
  {0,0,0,0,0,0,8,0},
  {0,0,0,0,0,3,0,0},
  {0,0,0,0,0,0,7,0},
  {0,0,0,0,0,0,5,0},
  {0,0,0,0,0,0,0,2},
  {0,0,0,0,0,0,0,6},
};

Answer 1

我想，“定向”是指定向。每条边仅允许沿一个方向行驶。

例如，权重为 5 的边 {1;3} 与顶点 3 相关

所以你有一条从 1 到 3 的边，权重为 5。所以你可以将该边添加到几乎任何图论库中，运行 Dijkstra 方法并毫不费力地得到答案。

例如使用 PathFinder 库（https://github.com/JamesBremner/PathFinder），输入如下所示

format costs
l 0 1 1
l 0 2 2
l 1 2 1
l 1 3 5
l 1 4 2
l 2 3 2
l 2 4 1
l 2 5 4
s 0
e 4

和输出