我需要使用(而不是实现)基于数组的 Dijkstras 算法版本。任务是给定一组线段(障碍)和起点/终点,我必须找到并绘制从起点/终点开始的最短路径。已经完成了计算部分等。但不知道如何在我的代码中使用 dijkstras。我的代码如下
class Point
{
public:
int x;
int y;
Point()
{
}
void CopyPoint(Point p)
{
this->x=p.x;
this->y=p.y;
}
};
class NeighbourInfo
{
public:
Point x;
Point y;
double distance;
NeighbourInfo()
{
distance=0.0;
}
};
class LineSegment
{
public:
Point Point1;
Point Point2;
NeighbourInfo neighbours[100];
LineSegment()
{
}
void main()//in this I use my classes and some code to fill out the datastructure
{
int NoOfSegments=i;
for(int j=0;j<NoOfSegments;j++)
{
for(int k=0;k<NoOfSegments;k++)
{
if( SimpleIntersect(segments[j],segments[k]) )
{
segments[j].neighbours[k].distance=INFINITY;
segments[j].neighbours[k].x.CopyPoint(segments[k].Point1);
segments[j].neighbours[k].y.CopyPoint(segments[k].Point2);
cout<<"Intersect"<<endl;
cout<<segments[j].neighbours[k].distance<<endl;
}
else
{
segments[j].neighbours[k].distance=
EuclidianDistance(segments[j].Point1.x,segments[j].Point1.y,segments[k].Point2.x,segments[k ].Point2.y);
segments[j].neighbours[k].x.CopyPoint(segments[k].Point1);
segments[j].neighbours[k].y.CopyPoint(segments[k].Point2);
}
}
}
}
现在我有了从每个 segmnet 到所有其他段的距离,amd 使用这个数据(在 neighbourinfo 中)我想使用基于数组的 Dijkstras(restriction)来追踪从起点/终点开始的最短路径。有更多代码,但有为方便读者缩短问题
请帮助!谢谢,请不要.net lib/code,因为我只使用核心C++ ..提前谢谢
但我需要基于数组的版本(严格..)我不打算使用任何其他实现。