Это продолжение Возвращается имя нижнего узла , только теперь с большим прогрессом и меньшим количеством ошибок.
Как и в прошлый раз, это для университетского курса, поэтомукопирование-вставка точно не будет для меня наиболее полезным, даже если оно работает.
Проблема, с которой я столкнулся сейчас, связана с индексацией векторов в функции LeastDistance, поскольку исключение времени выполнения генерируется, когдакод запускается как в отладчик, так и из него, с сообщением о том, что векторный индекс находится вне диапазона.Если кто-то более знаком с векторной библиотекой, чем я, соответствующая строка - 1804. Это срабатывает при доступе к циклу for в той же функции.
for (int j = 0; j < hnode[i].nodes.size(); j++)
Пока что я написал небольшую вспомогательную функцию, GetIndex, но я не уверен, что код для него правильный, и как реализовать его в самой функции LeastDistance.Полный код ниже (извините за плохое форматирование, редактор здесь доставил мне некоторое горе).
#include "stdafx.h"
#include<iostream>
#include<vector>
#define INF = 9999;
using namespace std;
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;
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 Destination);
void DestinationChangeCaller();
char GetStartNode();
int GetIndex(char CurrentNode);
};
int main()
{
Graph graph;
graph.createHeadNode('A');
graph.createHeadNode('B');
graph.createHeadNode('C');
graph.createHeadNode('D');
graph.createHeadNode('E');
graph.createAdjMatrix();
graph.GetStartNode();
graph.DestinationChangeCaller();
system("pause");
return 0;
}
void Graph::DestinationChangeCaller()
{
for (Destination = 'A'; Destination <= 'E'; Destination++)
{
Dijkstra(StartNode, Destination);
}
}
Graph::Graph()
{
}
int Graph::GetIndex(char node)
{
return(node - 'A');
}
void Graph::createHeadNode(char x)
{
hnode.push_back(x);
}
char Graph::GetStartNode() // elementary get function with no error correction.
{
char got;
cout << "Please enter a node from A-E to start from: ";
cin >> got;
cout << endl;
return got;
}
void Graph::createAdjMatrix()
{
hnode[0].nodes.push_back({ 'B', 4 });
hnode[0].nodes.push_back({ 'C', 1 });
hnode[1].nodes.push_back({ 'A', 4 });
hnode[1].nodes.push_back({ 'C', 2 });
hnode[1].nodes.push_back({ 'D', 1 });
hnode[2].nodes.push_back({ 'A', 1 });
hnode[2].nodes.push_back({ 'B', 2 });
hnode[2].nodes.push_back({ 'D', 3 });
hnode[2].nodes.push_back({ 'E', 1 });
hnode[3].nodes.push_back({ 'B', 1 });
hnode[3].nodes.push_back({ 'C', 3 });
hnode[3].nodes.push_back({ 'E', 1 });
hnode[4].nodes.push_back({ 'C', 1 });
hnode[4].nodes.push_back({ 'D', 1 });
}
void Graph::printAdjMatrix()
{
cout << "The adjacency list that represents the graph is :";
for (int i = 0; i < hnode.size(); i++)
{
cout << endl;
cout << hnode[i].Name << " -> ";
for (int j = 0; j < hnode[i].nodes.size(); ++j)
{
cout << hnode[i].nodes[j].nodeLink << ", " << hnode[i].nodes[j].cost << ", ";
}
}
cout << endl;
cout << endl;
cout << endl;
for (int i = 0; i < hnode.size(); i++)
{
cout << "Shortest distance from node " << Start << " to node " << hnode[i].Name << " is:" << weight[i] << endl;
cout << "Shortest path is : ";
for (int j = 0; j < path.size(); j++)
{
cout << path[j] << endl;
}
}
}
char Graph::LeastDistance(char node)
{
int smallest = 9999;
char smallestNode = node;
int idx = 0;
int i = GetIndex(node);
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;
idx = i;
}
}
hnode[idx].Visited = true;
TotalCost = TotalCost + smallest;
return(smallestNode);
}
void Graph::Dijkstra(char StartNode, char Destination)
{
CurrentNode = StartNode;
if (CurrentNode == Destination)
{
cout << "the start is the destination, therefore the cost will be 0." << endl;
}
else
{
cout << StartNode << "->";
while (true)
{
if (CurrentNode != Destination)
{
CurrentNode = LeastDistance(CurrentNode);
cout << CurrentNode << "->";
}
else if (CurrentNode == Destination)
{
cout << endl;
cout << "The total cost of this path is:" << TotalCost;
cout << endl;
TotalCost = 0;//reset cost
break;
}
}
}
}
edit: я изменил следующие строки сверху, ошибка исправлена, но выводвсе еще не так, как ожидалось.
class Graph
{
char Start;
char StartNode;
char CurrentNode;
char Destination;
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 Destination);
void DestinationChangeCaller(char Start);
char GetStartNode();
int GetIndex(char CurrentNode);
};
int main()
{
Graph graph;
graph.createHeadNode('A');
graph.createHeadNode('B');
graph.createHeadNode('C');
graph.createHeadNode('D');
graph.createHeadNode('E');
graph.createAdjMatrix();
graph.GetStartNode();
graph.DestinationChangeCaller(graph.GetStartNode());
system("pause");
return 0;
}
void Graph::DestinationChangeCaller(char Start)
{
for (Destination = 'A'; Destination <= 'E'; Destination++)
{
Dijkstra(Start, Destination);
}
}