Sửa lỗi bài tập Dijktra

**ichiase24h** · 27-07-2014, 04:19 PM

Nhờ các bậc tiền bối coi dum em bài nay vói, chạy hoài mà không ra[IMG]images/smilies/2.gif[/IMG][IMG]images/smilies/2.gif[/IMG]

Mã:

# include <iostream>
# include <fstream>
# include <string>
using namespace std;

# define VOCUC 1000000000;
void Read_File(string filename, int matran[][100], int &n)
{
	ifstream f;
	f.open(filename);
	if (f.good())
	{
		int x;
		f >> n;

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				f >> x; matran[i][j] = x;
			}
		}
	}
	else
	{
		cout << "Khong mo duoc file" << endl;
	}
	f.close();
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << matran[i][j] << "\t";
		}
		cout << endl;
	}

}

void Dijktra(int Nhan[], int Chiphi[], int n, int matran[][100])
{
	int i, k;
	int s, g;
	int min = -1;
	cin >> s >> g;
	bool *T = new bool[n];
	for (i = 0; i < n; i++)
	{
		T[i] = true;
		Chiphi[i] = VOCUC;
		Nhan[i] = -1;
	}
	Chiphi[s] = 0;
	T[s] = false;
	Nhan[s] = 0;
	while (T[g])
	{
		for (i = 0; i < n; i++)
		{
			if (!T[i] && (min == -1 || (Chiphi[i] < Chiphi[min])))
				min = i;
		}

		if (min != -1)
		{
			T[min] = false;
			for (k = 0; k < n; k++)
			{
				if (T[k] && matran[k][min] != 0)
				{
					if (Chiphi[k] > Chiphi[min] + matran[min][k])
					{
						Chiphi[k] = Chiphi[min] + matran[min][k];
						Nhan[k] = min;
					}
				}
			}
		}
	}
}


void main()
{
	int matran[100][100];
	int ChiPhi[100];
	int Nhan[100];
	int n;
	Read_File("input.txt", matran, n);
	cout << "Nhap dinh dau, dinh cuoi: ";
	Dijktra(Nhan, ChiPhi, n, matran);

	// Xuat duong di ngan nhat
	for (int i = 0; i < n; i++)
		cout << ChiPhi[i] << "\t";

}