所以我已经为此工作了几个小时,我感到非常沮丧。我不明白我在做什么错。
我正在使用Dijkstra的算法来使用邻接矩阵找到源顶点和其他4个顶点之间的最短路径。这背后的想法是,有5个往返的城市和航班,而且我需要找到最便宜的机票价格,还要考虑到中途停留的时间。
我正在遵循本书中的算法(采用伪代码)以及以下网站上的代码:http://vinodcse.wordpress.com/2006/05/19/code-for-dijkstras-algorithm-in-c-2/
我遇到的问题是在网站上的嵌套循环中,计数器i从1开始,我相信这就是为什么从源顶点到所有顶点的距离正确的原因,除了第一个在999不变。
例:
当前距离:999220 0115130
前身:0 3 0 2 2
所有这些距离都是正确的-即使我更改了源顶点-除了第一个保持不变的距离之外。
如果我将计数器i更改为0,则每个距离都会混乱,即
当前距离:0105 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;
}
最佳答案
这张支票不应该
if(adjecencyMatrix[v][i]>0)
像其余的比较一样,用
adjecencyMatrix[v][i][0].ticketPrice
完成?如果
adjecencyMatrix[v][i]
是一个数组,它将被转换为一个指针,并且该指针将始终比较大于0。数组到指针的衰减再次出现:)