如何计算2个顶点之间的所有最短路径

本文关键字：之间 最短路径 顶点 2个 何计算 计算 | 更新日期: 2023-09-27 18:27:33

因此，如果我在图中有两个顶点，并且它们通过多条边连接，同时它们之间具有相同的最短路径（即，如果我有节点a和节点B，并且它们直接通过三条边连接（它们之间有3条最短路径，每条距离为1），则计数应返回3）我如何修改BFS算法来实现这一点？这是我的代码，它只计算2个节点之间的最短路径，而不计算这些最短路径的数量。

public void BFSDegree(Graph g, string s, string p)
    {
        Queue<string> q = new Queue<string>();
        dist.Add(s, 0);       
        q.Enqueue(s);
        while (q.Count() != 0)
        {
            string j = q.Dequeue();
            foreach (string h in g.adjacentTo(j))
            {
                if (!dist.ContainsKey(h))
                {
                    q.Enqueue(h);
                    dist.Add(h, 1 + dist[j]);
                }
                if (j == p)
                {
                    Console.WriteLine("               " + dist[j]);
                    return;
                }
            }
        }
    }

如何计算2个顶点之间的所有最短路径

如果一个节点u有x条最短路径，那么通过它发现的相邻节点v将有x乘以y的最短路径。其中y是从u到v的边数。此外，如果v可以通过其他相邻节点（具有相同的路径长度）到达，那么它的最短径数将是为每个父节点计算的所有xy因子的总和。

因此，该算法将与您的原型大不相同。我建议使用一个主循环，在每次迭代中增加当前长度，然后通过查看队列中节点的所有未访问的相邻节点来处理队列，计算这些相邻节点的xy因子之和，然后清除队列，并为下一次迭代对所有相邻节点进行排队（并将其标记为已访问）。在第一次迭代中，路径长度为0，队列仅包含源节点。

public void BFSDegree(Graph g, string s, string p)
{
    Queue<string> q = new Queue<string>();
    HashMap<string, int> path_counts = new HashMap<string, int>();
    path_counts.put(s, 1);       
    q.Enqueue(s);
    while (q.size()>0)
    {
        HashMap<string, int> adj_nodes = new HashMap<string, int>();
        foreach (string j in q) 
        {
            foreach (string h in g.adjacentTo(j))
            {
                if (!path_counts.ContainsKey(h))
                {
                    int count = 0;
                    if (adj_nodes.containsKey(h))
                        count=adj_nodes.get(h);
                    count += path_counts.get(j);
                    adj_nodes.put(h, count);
                }
            }
        }
        if (adj_nodes.containsKey(p))
        {
            Console.WriteLine("               " + adj_nodes.get(p));
            return;
        }
        path_counts.putAll(adj_nodes);
        q.clear();
        q.addAll(adj_nodes.keySet());
    }
}

在foreach之前，初始化变量int pathCount = 0;

然后，代替return;递增pathCount。

在foreach之后，检查是否为pathCount > 0，如果是，则返回。当然，您必须将返回类型更改为int。

相关文章：