Возвращаем имя нижнего узла - PullRequest
Новая
       12

Возвращаем имя нижнего узла

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

Прежде всего, это часть университетского курса, так что, хотя решение для копирования и вставки подойдет, я ищу немного больше глубины.Я все равно буду встречаться с моим руководителем завтра.

Теперь о проблеме.Я реализую алгоритм Дейкстры для 5 связанных узлов, AE, чьи связанные с ними затраты и ссылки хранятся в векторе; 

struct Node
{
    char nodeLink;  //adjacent link
    int cost;       //cost of a link
};                  //to use in Dijkstra algorithm


class HeadNode
{
public:
    char Name;
    bool Visited;
    vector<Node> nodes;
    HeadNode(char x) { Name = x; Visited = false; }

};

class Graph
{
    char Start = 'A';
    char StartNode;
    char CurrentNode;
    char Destination = 'E';
    int TotalCost = 0;
    vector<HeadNode> hnode;
    vector<char> path;
    vector<int> weight;

public:
    Graph();
    void createHeadNode(char X);
    void createAdjMatrix();
    char LeastDistance(char node);
    void printAdjMatrix();
    void Dijkstra(char StartNode);
    char GetStartNode();
};



int main()
{   
    Graph graph;
    graph.createHeadNode('A');
    graph.createHeadNode('B');
    graph.createHeadNode('C');
    graph.createHeadNode('D');
    graph.createHeadNode('E');

    graph.createAdjMatrix();
    //graph.printAdjMatrix();
    graph.Dijkstra(graph.GetStartNode());

    system("pause");
    return 0;
}

Graph::Graph()
{
}


void Graph::createHeadNode(char x)
{
    hnode.push_back(x);

}

Чтобы правильно реализовать алгоритм, я создал функцию-предшественник, LeastDistance (), внутри графа классов.У меня также есть функция для получения начального узла, но это здесь не особенно важно; 

char Graph::LeastDistance(char node)
{
    int smallest = 9999;
    char smallestNode;

    for (int i = 0; i < hnode.size(); i++)
    {
        for (int j = 0; j < hnode[i].nodes.size(); ++j)
        {
            if ((node == hnode[i].Name) && (hnode[i].nodes[j].cost <= smallest) && (hnode[i].Visited == false))
            {
                smallest = hnode[i].nodes[j].cost;
                smallestNode = hnode[i].nodes[j].nodeLink;
            }
            else
            {
                hnode[i].Visited = true;
                break;
            }
        }
    }
    TotalCost = TotalCost + smallest;
    return(smallestNode);
}

void Graph::Dijkstra(char StartNode)
{
    CurrentNode = StartNode;
    if (CurrentNode == Destination)
    {
        cout << "the start is the destination, therefore the cost will be 0." << endl;
    }
    else
    {
        while(true)
        {
            if (CurrentNode != Destination)
            {
                CurrentNode = LeastDistance(StartNode);
                cout << CurrentNode << "<-";
            }
            else if (CurrentNode == Destination)
            {
                cout << endl;
                cout << "The total cost of this path is:" << TotalCost;
                TotalCost = 0;//reset cost
                break;
            }
        }
    }

}

Моя проблема в том, что функция LeastDistance всегда возвращает узел C, что приводит к его повторной печати инад, так что заполняет консоль.До сих пор я пытался отлаживать с помощью visual studio 2017, но не могу понять смысл часов.Я также изменил порядок перерывов и попытался убедиться, что флаг посещения установлен в значение true.не влияет ли на это какой-либо приоритет операций, я не уверен.

Заранее спасибо.

1 Ответ

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

Я бы сказал, что у вас есть множество проблем с тем, как вы реализуете это ... но я думаю, что одна из причин, которая вызывает у вас проблему, которую вы описываете, это утверждение прямо здесь: 

if (CurrentNode != Destination)
{
    CurrentNode = LeastDistance(StartNode);
    cout << CurrentNode << "<-";
}

Подумайте о том, чтоэто делает.Допустим, ваш первый узел не тот, который вы ищете, затем вы называете наименьшее расстояние и находите следующий наименьший узел.Затем вы печатаете это.Затем вы снова итерируете цикл while, только чтобы найти, что CurrentNode не тот, который вы ищете, поэтому вы снова вызываете LeastDistance(StartNode), который вернет точно такое же значение.Таким образом, вы будете продолжать печатать тот же результат, который, по-видимому, равен c.

Если предположить, что все остальное правильно, я думаю, вы хотите: 

CurrentNode = LeastDistance(CurrentNode);
...