c++ - Dijkstra 的算法问题 [转贴]

Question

我意识到由于我的低代表率或其他原因我无法发布我自己的问题的答案所以我删除了我的旧问题并重新提出它。我改变了一些东西，但仍然无法得到我正在寻找的东西。

这里是大部分代码我省略了一些更简单的实现，例如 pathFinder 类的一部分，因为我确信它们可以工作，这就是为什么您会在那里随机看到 playerVertex 和时间。在示例中，他们使用了 decreaseKey 函数，我不确定这是否正是我所缺少的？我是这里的初学者，所以欢迎建设性的批评。 (希望尽可能有礼貌)大声笑。我的问题是打印路径，我一遍又一遍地得到相同的两个值的循环。

class Heap 
{
public: Heap();
    ~Heap();
    void insert(double element);
    double  deletemin();
    void print();
    int size(){return heap.size();}


private:
 int currentIndex;
 int left(int parent);
 int right(int parent);
 int parent(int child);
 void heapifyup(int index);
 void heapifydown(int index);
private:
 vector<double> heap;
};

Heap::Heap()
{
 currentIndex = 0;
}
Heap::~Heap()
{}

void Heap::insert(double element)
{
heap.push_back(element);
currentIndex++;
heapifyup(heap.size() - 1);
}

double Heap::deletemin()
{
double min = heap.front();
heap[0] = heap.at(heap.size()-1);
heap.pop_back();
heapifydown(0);
currentIndex--;
return min;
}
void Heap::print()
{
vector<double>::iterator pos = heap.begin();
cout << "Heap = ";
while ( pos != heap.end() ) 
{
    cout << *pos;
    ++pos;
    cout << endl;
 }
}
void Heap::heapifyup(int index)
{


while((index>0) && (parent(index) >=0) && (heap[parent(index)] > heap[index]))
{
 double tmp = heap[parent(index)];
 heap[parent(index)] = heap[index];
 heap[index] = tmp;
 index = parent(index);


}
}

void Heap::heapifydown(int index)
{



int child = left(index);

if((child > 0) && (right(index) > 0) && (heap[child]>heap[right(index)]))
{
 child = right(index);

}
if(child > 0)
{
double tmp = heap[index];
heap[index] = heap[child];
heap[child] = tmp;
heapifydown(child);
}
}

int Heap::left(int parent)
{
int i = ( parent <<1) + 1; 
return(i<heap.size()) ? i : - 1;
}

int Heap::right(int parent)
{
int i = ( parent <<1) + 2; 
return(i<heap.size()) ? i : - 1;
}

int Heap::parent(int child)
{
if(child != 0)
{
 int i = (child - 1) >>1;
 return i;
}
return -1;
}



class pathFinder : public weightedGraph
{

private:

vertex* playerVertex;
double time;


public:
string source;
pathFinder()
{
    playerVertex = NULL;
    time = 0;

}


  void Dijkstra(int s,int t)
{
    vertex *verts = findVertex(grid[s][t]);
    Heap H;
    for each(vertex *v in vertexList)
    {

        if(v->data == verts->data)
        {
            verts->distance = 0;
            verts->pred = NULL;
        }
        v->distance = INFINITY;
        v->pred = NULL;
        H.insert(v->data);
    }
    while(H.size() != 0)
    {

        vertex *x = findVertex(H.deletemin());

        for each(edge *v in x->adjacencyList)
        {

            if(v->end->visited != true)
            {    
            relax(x,v->end);
            v->end->visited = true;
            }
            else
                break;

        }

    }
}








void relax(vertex *a, vertex *b)
{

    if(a->distance + weightFrom(a,b) > b->distance)
        {
            b->distance = a->distance + weightFrom(a,b);
            b->pred = a;
        }


}


void printPath(double dest,double dest1)
{
    vertex *verta = findVertex(dest);
    while(verta->pred->data != dest1)
    {
    cout<<verta->data<<endl;
    verta = verta->pred;
    }
}

我不确定打印路径是什么。我只是使用了我之前实现的 BFS 算法的打印路径。

Answer 1

您在 printPath 函数的哪个位置寻找列表的末尾？

你继续 verta = verta->pred 直到数据不等于某个值。

顺便说一句，不要比较 double 是否相等，因为这不会发生。参见 What Every Computer Scientist Should Know About Floating Point.

单步执行调试器会发生什么？
(尝试绘制链接以及如何遍历它们。)