在有向图中创建最短路径的数量

Question

我的作业是使用c语言创建有向图中从S到任何其他顶点的最短路径的数量

图表显示为 txt 文件，如下所示:

3 // number of vertex in G
{2,3},{1},{} // in the first {} we can see the neighbors for V1 , in the second for V2 and so on

我必须打印 s 的最短路径数的数组

我使用的算法类似于 BFS，但添加了一些内容:numOfShortest(G,S)

for vertex x which belongs to gropu V-S 
do color[x]=white, d[x]=0, F[x]=0
color[s]=gray,d[s]=0,F[s]=1
while Q is not empty //= let Q be a queue
 do u=dequeue(Q)
  for each vertex v = N(u) // = for every neighbor of u
   do if color[v] = white 
    then color[v]= gray, d[v]=d[u]+1 
       F[v]=f[v]+f[u] // = v must have atleast the same number of paths as u
       enqueue(Q,v)
      else if color[v]=gray 
       then if d[u] < d[v]
        then f[v]=f[v]+f[u]
  color[u]=black // = when finished with every N(u) 

现在我必须考虑一些事情(如果我错了请纠正我)

• 使用链表实现排队
• 为每个 v 创建一个名为 vertex 的结构，其中包含邻居(使用动态数组)
• 我需要以某种方式将文件上写的邻居扫描到结构体顶点上的邻居

也许我的准备工作做得太过分了，有一个更简单的方法可以做到这一点，但我脑子里有些困惑。感谢任何可以提供帮助的人

Answer 1

您应该开始了解 Dijkstra 算法，以获取图中从一个顶点 S 到每个其他顶点的最短路径。

那么也许将它与类似 BFS 的算法混合将帮助你计算你的意思。