C++计算有向图中的最短路径

Question

我的任务是编写一个程序来维护简单网络(加权有向图)的表示，并根据请求计算两个给定节点之间的最佳路径。

目前，我正在尝试编写一个函数来计算两个节点之间最简单的函数，但是，在尝试运行我的程序时，我遇到了两个特定的错误

Severity    Code    Description Project File    Line    Suppression State
Error   C3863   array type 'bool [openNode]' is not assignable  P   127 

和

Severity    Code    Description Project File    Line    Suppression State
Error   C3863   array type 'int [openNode]' is not assignable   

我无法调试，因为这两个主要错误不允许我的程序运行。这些错误有什么特别的原因吗？

提前致谢!

这是Graph.h中定义的节点结构

struct GraphNode
{
    char ID;
    std::string name;
    int inNodes = 0;
    int outNodes = 0;
    std::vector<std::pair<GraphNode*, int>> connection;
    int  connections = 0;
};

这是导致错误的特定代码。

#include "Graph.h"

std::vector<GraphNode*> _graph;
int openNode = 0;

//Obligatory constructor
void Graph()
{

}

void shortestPath(char fromNode, char toNode)
{
    bool known[openNode];
    int distance[openNode];
    GraphNode*  previous[openNode];
    int numbChecked = 0;


    for (int i = 0; i < openNode; i++)
    {
        known[i] = false;
        distance[i] = 999999;
        previous[i] = nullptr;
    }

    distance[findNode(fromNode)] = 0;

    while (numbChecked < openNode)
    {
        int smallestUnknown = 9999999;
        int locationOfSmall = 0;
        for (int i = 0; i < openNode; i++)
        {
            if (known[i] == false && distance[i] < smallestUnknown)
            {
                smallestUnknown = distance[i];
                locationOfSmall = i;
            }
        }

        if (distance[locationOfSmall] == 0)
        {
            previous[locationOfSmall] = nullptr;
        }

        known[locationOfSmall] = true;
        numbChecked++;

        if (_graph[locationOfSmall]->outNodes > 0)
        {
            for (int i = 0; i < _graph[locationOfSmall]->outNodes; i++)
            {
                int newDistanceLocation = findNode(_graph[locationOfSmall]->connection[i].first->ID);
                if (known[newDistanceLocation] == false && (distance[locationOfSmall] + _graph[locationOfSmall]->connection[i].second) < distance[newDistanceLocation])
                {
                    distance[newDistanceLocation] = distance[locationOfSmall] + _graph[locationOfSmall]->connection[i].second;
                    previous[newDistanceLocation] = _graph[locationOfSmall];
                }
            }
        }
    }

    int destination = findNode(toNode);
    std::string output;
    std::string charTransfer;
    charTransfer = toNode;
    output = charTransfer;

    while (previous[destination] != nullptr)
    {
        destination = findNode(previous[destination]->ID);
        charTransfer = _graph[destination]->ID;
        output = charTransfer + "->" + output;
    }

    if (_graph[destination]->ID != fromNode)
    {
        std::cout << "The nodes are not connected." << std::endl;
    }
    else
    {
        std::cout << "The path is: " << output << std::endl;
        std::cout << "The distance is: " << distance[findNode(toNode)] << std::endl;
    }

}

如有任何更改建议，我们将不胜感激!

Answer 1

shortestPath 函数开头的代码无效:

bool known[openNode];
int distance[openNode];
GraphNode*  previous[openNode];

你不能使用变量在堆栈上创建数组(这是你试图在那里做的)，因为编译器在编译时不知道 openNode 的值(这是需要的以确定堆栈大小)。

为什么不使用 vector ，例如:

std::vector<bool> known(openNode, false);
std::vector<int> distance(openNode, 999999);
std::vector<GraphNode*>  previous(openNode, nullptr);

使用此方法也会使下面的 for 循环过时。