如何修改Dijkstra算法以打印源节点到可达节点的分支数？

问题需求 #

需要修改现有Dijkstra算法代码，使其能够打印源节点到其他所有可达节点之间的最短路径分支数量（即到达该节点的最短路径的条数）。原代码尝试引入计数器但未成功，原代码如下：

int minDistance(Graph g,double dist[], bool sptSet[])
{
// Initialize min value
int min = INT_MAX, min_index;
for (int v = 0; v < g.n ; v++)
    if (sptSet[v] == false && dist[v] <= min)
        min = dist[v], min_index = v;
    return min_index;
}
void printSolution(Graph g,double dist[])
{
    cout<<"Vertex Distance from Source\n";
    for (int i = 0; i < g.n; i++)
    if (dist[i] < g.n)
    {
        cout<< i+1 << "         " << dist[i] << endl;
    }
}
void dijkstra(GRAPH g, int src)
{
    double dist[MAX];
    bool sptSet[MAX];
    for (int i = 0; i < g.n; i++)
        dist[i] = INT_MAX, sptSet[i] = false;
    dist[src] = 0;
    for (int count = 0; count < g.n - 1; count++) 
    {
        int u = minDistance(g, dist, sptSet);
        sptSet[u] = true;
        for (int v = 0; v < g.n; v++) {
            int c = 0; //Here I tried to introduce a counter!
            if (!sptSet[v] && g.ms[u][v] && dist[u] != INT_MAX && 
                    dist[u] + g.ms[u][v] < dist[v])
            {
                c++; //Here I tried to introduce a counter!
                dist[v] = dist[u] + g.ms[u][v];
            }
             cout << c; //Here I tried to introduce a counter!
        }
    }
    printSolution(g, dist);
}

修改方案 #

核心思路是新增一个数组pathCount来记录每个节点的最短路径数量，在松弛操作时根据路径长度的更新情况维护这个数组：

修改后的完整代码 #

#include <iostream>
#include <climits>
using namespace std;

// 假设Graph/GRAPH结构体定义如下（需根据实际情况补充）
struct Graph {
    int n;
    double ms[MAX][MAX]; // 邻接矩阵，存储边权
};
typedef Graph GRAPH;

int minDistance(Graph g, double dist[], bool sptSet[])
{
    int min = INT_MAX, min_index;
    for (int v = 0; v < g.n ; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

// 修改printSolution，新增路径数量打印
void printSolution(Graph g, double dist[], int pathCount[])
{
    cout << "Vertex | Distance from Source | Number of Shortest Paths\n";
    cout << "---------------------------------------------------------\n";
    for (int i = 0; i < g.n; i++)
    {
        if (dist[i] != INT_MAX) // 只打印可达节点
        {
            cout << "  " << i+1 << "   |         " << dist[i] << "         |          " << pathCount[i] << endl;
        }
    }
}

void dijkstra(GRAPH g, int src)
{
    double dist[MAX];
    bool sptSet[MAX];
    int pathCount[MAX]; // 新增数组，记录每个节点的最短路径数量

    // 初始化：距离设为无穷，sptSet设为false，路径数初始为0
    for (int i = 0; i < g.n; i++)
    {
        dist[i] = INT_MAX;
        sptSet[i] = false;
        pathCount[i] = 0;
    }
    dist[src] = 0;
    pathCount[src] = 1; // 源节点到自己有1条路径

    for (int count = 0; count < g.n - 1; count++) 
    {
        int u = minDistance(g, dist, sptSet);
        sptSet[u] = true;

        for (int v = 0; v < g.n; v++) 
        {
            // 仅当v未被处理、u和v之间有边、u可达时进行判断
            if (!sptSet[v] && g.ms[u][v] != 0 && dist[u] != INT_MAX)
            {
                // 情况1：找到更短的路径
                if (dist[u] + g.ms[u][v] < dist[v])
                {
                    dist[v] = dist[u] + g.ms[u][v];
                    pathCount[v] = pathCount[u]; // 重置路径数为u的路径数
                }
                // 情况2：找到长度相同的最短路径，累加路径数
                else if (dist[u] + g.ms[u][v] == dist[v])
                {
                    pathCount[v] += pathCount[u];
                }
            }
        }
    }
    printSolution(g, dist, pathCount);
}

关键改动说明 #

1. 新增pathCount数组：用于存储每个节点的最短路径数量，初始化时源节点的路径数为1，其余为0。
2. 松弛操作的逻辑优化：
   • 当找到更短的路径时，将目标节点的路径数重置为当前节点的路径数（因为所有到当前节点的最短路径加上这条边就是到目标节点的新最短路径）。
   • 当找到长度相同的最短路径时，将目标节点的路径数累加当前节点的路径数（新增了一条最短路径分支）。
3. 修改printSolution函数：新增路径数量的打印，并且修正了可达节点的判断逻辑（原代码dist[i] < g.n不合理，改为判断是否不等于无穷大）。

内容的提问来源于stack exchange，提问作者Andew Tayloe