Что не так в моей реализации алгоритма Дейкстры?

Question

[callmehyu]

Есть задание: написать программу, которая считает минимальные расстояния до вершин в графе методом Дейкстры. Протестировать на графах с 5000 и 9000 вершинами. Написал код:

#include <cstdlib>
#include <iostream>
#include <iomanip>

using namespace std;

int main() {
	const int inf = 1000000;
	srand(time(NULL));
	int n;
	cout << "Enter the number of vertices:" << endl;
	cin >> n;
	int **w;
	w = new int *[n];
	for (int i = 0; i < n; i++) {
		w[i] = new int[n];
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			w[i][j] = 0;
			w[i][j] = rand() % 100;
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j) w[i][j] = 0;
			else w[i][j] = w[j][i];
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << setw(5) << w[i][j];
		}
		cout << endl;
	}
	
	int *d = new int [n];
	int *v = new int [n];
	
	for (int i = 0; i < n; i++) {
		d[i] = inf;
		v[i] = 1;
	}
	
	cout << "Enter the number of the vertex for which you want to find distances: ";
	int ind;
	cin >> ind;
	ind--;
	d[ind] = 0;
	
	int minIndex, min, temp, counter = 0;
	
	do {
		minIndex = inf;
		min = inf;
		
		for (int i = 0; i < n; i++) {
			if((v[i] == 1) && (d[i] < min)) {
				min = d[i];
				minIndex = i;
			}
		}
		
		if (minIndex != inf) {
			for (int i = 0; i < n; i++) {
				if (w[minIndex][i] > 0) {
					temp = min + w[minIndex][i];
					if (temp < d[i]) {
						d[i] = temp;
					}
				}
				counter++;
			}
			v[minIndex] = 0;
		}
	} while (minIndex < inf);
	
	for (int i = 0; i < n; i++) {
		cout << setw(5) << d[i];
	}
	cout << endl;
	cout << "Number of iterations: " << counter << endl;
	system("pause");
	return 0;
}

Но все расстояния оказываются в диапазоне 1-4. Пробовал прогонять 100 вершин, в таком случае считает нормально. В чем может быть проблема?

Answer 1

[Евгений Залецкий]

Посмотри данный код

Comments

[callmehyu]

Посмотрел, но всё равно не понял что не так с моим кодом