Так что я работал над этим часами, и я очень расстроен. Я не понимаю, что я делаю не так.
Я использую алгоритм Дейкстры, чтобы найти кратчайшие пути между исходной вершиной и 4 другими вершинами, используя матрицу смежности. Идея заключается в том, что туда и обратно отправляются 5 городов и рейсов, и мне нужно найти самую дешевую цену билета с учетом задержек.
Я придерживаюсь алгоритма из моей книги, которая находится в псевдокоде, и кода на следующем веб-сайте: http://vinodcse.wordpress.com/2006/05/19/code-for-dijkstras-algorithm-in-c-2/
У меня проблема в том, что во вложенном цикле for на веб-сайте счетчик i начинается с 1, и я считаю, что это причина, почему расстояния от исходной вершины до всех вершин верны, за исключением первого, который остается неизменным на 999.
Пример:
Текущее расстояние: 999 220 0 115 130
Предшественники: 0 3 0 2 2
Все эти расстояния правильны - даже если я изменяю исходную вершину - за исключением первой, которая остается неизменной.
Если я изменю счетчик i на 0, он портится на каждом расстоянии, т.е.
Текущее расстояние: 0 105 0 0 0
В любом случае, пожалуйста, помогите. Вот соответствующий код.
void Graph::findDistance(int startingVertex)
{
for(int i=0; i<MAX;i++)
{
currentDistance[i] = 999;
toBeChecked[i] = 1;
predecessor[i] = 0;
}
currentDistance[startingVertex]=0;
bool flag=true;
int v;
while(flag)
{
v=minimum();
toBeChecked[v]=0;
for(int i=1; i<MAX;i++) //here is where i think im going wrong
{
if(adjecencyMatrix[v][i]>0)
{
if(toBeChecked[i]!=0)
{
if(currentDistance[i] > currentDistance[v]+adjecencyMatrix[v][i][0].ticketPrice)
{
currentDistance[i] = currentDistance[v]+adjecencyMatrix[v][i][0].ticketPrice;
predecessor[i]=v;
}
}
}
}
flag = false;
for(int i=1; i<MAX;i++)
{
if(toBeChecked[i]==1)
flag=true;
}
}
}
int Graph::minimum()
{
int min=999;
int i,t;
for(i=0;i<MAX;i++)
{
if(toBeChecked[i]!=0)
{
if(min>=currentDistance[i])
{
min=currentDistance[i];
t=i;
}
}
}
return t;
}