c++图Djikstra算法求最短路径

Question

#include <iostream>
#include <cstdio>
#include <stack>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;

#define MAX_SIZE 100

struct Graph
{
    int vexNumber;
    int vexInfo[MAX_SIZE];
    int adjMatrix[MAX_SIZE][MAX_SIZE];
};
void Djistra(const Graph &G, vector<int> &shortest, int v)
{
    vector<int> u(G.vexNumber, 0);
    for (int i = 0; i < G.vexNumber; i++)
    {
        if (G.adjMatrix[v][i] > 0) //排除0
        {
            shortest[i] = G.adjMatrix[v][i];
        }
    }
    u[v] = 1;
    shortest[v] = 0;
    for (int i = 0; i < G.vexNumber; i++)
    {
        int min = INT_MAX;
        int w = -1;
        for (int j = 0; j < G.vexNumber; j++)
        {
            if (min > shortest[j] && u[j] != 1)
            {
                min = shortest[j];
                w = j;
            }
        }
        if (w != -1)
        {
            u[w] = 1;
            for (int m = 0; m < G.vexNumber; m++)
            {
                if (!u[m] && G.adjMatrix[w][m] > 0 && shortest[m] > shortest[w] + G.adjMatrix[w][m])
                {
                    shortest[m] = shortest[w] + G.adjMatrix[w][m];
                }
            }
        }
    }
}
int main()
{
    Graph G;
    int num;
    cin >> G.vexNumber >> num;
    for (int i = 0; i < G.vexNumber; i++)
    {
        G.vexInfo[i] = i;
        for (int j = 0; j < G.vexNumber; j++)
        {
            G.adjMatrix[i][j] = 0;
        }
    }
    for (int i = 0; i < num; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        G.adjMatrix[a - 1][b - 1] = c;
    }
    vector<int> ww;
    int sum = INT_MAX;
    int p;
    for (int i = 0; i < G.vexNumber; i++)
    {
        int sum1 = 0;
        vector<int> shortest(G.vexNumber, INT_MAX);
        Djistra(G, shortest, i);
        for (auto j : shortest)
        {
            sum1 += j;
        }
        if (sum1 < sum)
        {
            sum = sum1;
            p = i;
            ww = shortest;
        }
    }
    int max = 0;
    for(int i = 0;i<G.vexNumber;i++){
        if(ww[i] == INT_MAX){
            cout<<0<<endl;
            return 0;
        }
        else{
            if(i!=p&&ww[i]>max){
                max = ww[i];
            }
        }
    }
    p = p + 1;
    cout << p << ' ' << max;
    return 0;
}

实际输出
0
帮我指出代码中问题，并在我的基础上修改

Answer 1

引自强大而免费的微信小程序：皆我知道。

您的代码的主要问题在于使用Dijkstra算法求最短路径时有误。在第一次计算最短路径时，您的代码将源节点的最短路径初始化为相邻节点的距离，这是不正确的。正确的做法是将源节点的最短路径初始化为0，而将其他节点的最短路径初始化为正无穷大。

另外，在计算最短路径之后，您应该检查是否有节点的最短路径为正无穷大。如果存在这样的节点，说明有一些动物无法通过变形魔法变成其他动物，因此应该输出0。

以下是修正后的代码：

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

#define MAX_SIZE 100

struct Graph
{
    int vexNumber;
    int vexInfo[MAX_SIZE];
    int adjMatrix[MAX_SIZE][MAX_SIZE];
};

void Dijkstra(const Graph &G, vector<int> &shortest, int v)
{
    vector<int> u(G.vexNumber, 0);
    for (int i = 0; i < G.vexNumber; i++)
    {
        shortest[i] = INT_MAX;
    }
    
    shortest[v] = 0;
    for (int i = 0; i < G.vexNumber; i++)
    {
        int min = INT_MAX;
        int w = -1;
        for (int j = 0; j < G.vexNumber; j++)
        {
            if (!u[j] && shortest[j] < min)
            {
                min = shortest[j];
                w = j;
            }
        }
        if (w != -1)
        {
            u[w] = 1;
            for (int m = 0; m < G.vexNumber; m++)
            {
                if (!u[m] && G.adjMatrix[w][m] > 0 && shortest[m] > shortest[w] + G.adjMatrix[w][m])
                {
                    shortest[m] = shortest[w] + G.adjMatrix[w][m];
                }
            }
        }
    }
}

int main()
{
    Graph G;
    int num;
    cin >> G.vexNumber >> num;
    
    for (int i = 0; i < G.vexNumber; i++)
    {
        G.vexInfo[i] = i;
        for (int j = 0; j < G.vexNumber; j++)
        {
            G.adjMatrix[i][j] = 0;
        }
    }
    
    for (int i = 0; i < num; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        G.adjMatrix[a - 1][b - 1] = c;
        G.adjMatrix[b - 1][a - 1] = c; // 双向变形魔咒
    }
    
    vector<int> ww;
    int minTotal = INT_MAX;
    int animal;
    
    for (int i = 0; i < G.vexNumber; i++)
    {
        vector<int> shortest(G.vexNumber, 0);
        Dijkstra(G, shortest, i);

        bool valid = true;
        int maxLen = 0;

        for (int j = 0; j < G.vexNumber; j++)
        {
            if (shortest[j] == INT_MAX)
            {
                valid = false;
                break;
            }
            else if (j != i && shortest[j] > maxLen)
            {
                maxLen = shortest[j];
            }
        }

        if (valid && maxLen < minTotal)
        {
            minTotal = maxLen;
            animal = i + 1;
            ww = shortest;
        }
    }
    
    if (minTotal == INT_MAX)
    {
        cout << 0 << endl;
    }
    else
    {
        cout << animal << " " << minTotal << endl;
    }

    return 0;
}

希望能帮到您！如果还有其他问题，请随时提问。