C ++ Расчет кратчайшего пути в ориентированном графе - PullRequest
Новая
       48

C ++ Расчет кратчайшего пути в ориентированном графе

0 голосов
/ 06 мая 2018

Мне поручено написать программу для поддержки представления простой сети (взвешенного ориентированного графа) и вычисления наилучшего пути между двумя заданными узлами по запросу.

В настоящее время я пытаюсь написать функцию для вычисления простейшего между двумя узлами, однако при попытке запустить мою программу я получаю две конкретные ошибки 

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;
    }

}

Любые предложения по изменению будут высоко оценены!

1 Ответ

0 голосов
/ 06 мая 2018

В начале вашей функции shortestPath указан неверный код: 

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

Вы не можете использовать переменные для создания массивов в стеке (что вы и пытаетесь сделать там), потому что компилятор не знает значение openNode во время компиляции (что необходимо для определения размера стека) ).

Почему бы вам не использовать вектор, например: 

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

Использование этого метода делает цикл for ниже устаревшим.

...