Алгоритм Дейкстры, использующий матрицу смежности, не находит правильное расстояние / путь от каждого узла до каждого другого узла

Я пытаюсь написать программу, которая строит график с использованием матрицы смежности, а затем находит кратчайший путь от каждого узла к каждому другому узлу, используя алгоритм Дейкстры. Моя программа не может найти правильные кратчайшие пути каждый раз. Мне также нужно проследить путь, но я не уверен, с чего начать.

class GraphD
{

public:
GraphD();
void buildGraph(ifstream &infile);

void insertEdge(int from, int to, int distance);

void findShortestPath();

private:
static const int MAXNODES = 101;
static const int infinity = 2147483647;
struct TableType
{
bool visited;
int dist;
int path;
};
int C[MAXNODES][MAXNODES]; // holds adjacency matrix
int size;
TableType T[MAXNODES][MAXNODES]; // for dijkstra's algorithm
};#include "GraphD.h"
GraphD::GraphD()
{
size = 0;
for(int i = 1; i < MAXNODES; i++)
{
for(int j = 1; j < MAXNODES; j++)
{
C[i][j] = infinity;
T[i][j].dist = infinity;
T[i][j].visited = false;
T[i][j].path = 0;
}
}
}

void GraphD::buildGraph(ifstream &infile)
{
string line;
if(getline(infile, line))
{
size = atoi(line.c_str());
for(int i = 1; i <= size; i++)
{
getline(infile, line);
data[i] = line;
}

int vertex1, vertex2, distance;
while(getline(infile, line))
{
stringstream edge(line);
edge >> vertex1 >> vertex2 >> distance;
if(vertex1 == 0)
break;
insertEdge(vertex1, vertex2, distance);
}
for(int i = 1; i <= size; i++)
{
C[i][i] = 0;
}
}
}

void GraphD::insertEdge(int from, int to, int distance)
{
C[from][to] = distance;
}

void GraphM::findShortestPath()
{
for(int source = 1; source <= size; source++)
{
T[source][source].dist = 0;
for(int i = 1; i <= size; i++)
{
int v = 0;
int shortestDistance = infinity;
for(int j = 1; j <= size; j++)
{
if((C[source][j] < shortestDistance) && !T[source][j].visited)
{
shortestDistance = C[source][j];
v = j;
}
}
T[source][v].visited = true;
for(int w = 1; w <= size; w++)
{
if(!T[v][w].visited)
{
T[v][w].dist = min(T[v][w].dist, T[source][v].dist + C[v][w]);
}
}
}
}
}

0

Решение

Установите значение бесконечности равным 1’000’000’000 (или что-то подобное), потому что при использовании значения MAX_INT вы получаете здесь целочисленное переполнение

T[v][w].dist = min(T[v][w].dist, T[source][v].dist + C[v][w]);

Кроме того, я думаю, что вы должны заменить следующую часть кода

if(!T[v][w].visited)
{
T[v][w].dist = min(T[v][w].dist, T[source][v].dist + C[v][w]);
}

к следующему

if(!T[source][w].visited)
{
T[source][w].dist = min(T[source][w].dist, T[source][v].dist + C[v][w]);
}

потому что вам нужно найти расстояние до вершины W от вершины источника, а не V.

-1

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

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