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

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

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

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

Решение

У вас есть неверный код в начале вашего 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 ниже устаревшим.

2

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector