0

ダイクストラアルゴの配列ベースのバージョンを使用する（実装しない）必要があります。タスクは、一連の線分（障害物）と開始/終了ポイントを指定して、開始/終了ポイントから最短パスを見つけて描画する必要があることです。計算部分などを行ったが、私のコードでダイクストラを使用する方法がわからない。私のコードは次のとおりです。

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);

}
}
}

}

これで、各セグメントから他のすべてのセグメントまでの距離がわかりました。このデータを使用してamd（neighbourinfo内）配列ベースのダイクストラ（制限）を使用して、開始点/終了点からの最短経路をトレースします。コードは他にもありますが、読者の使いやすさのために問題を短縮しました

助けてください!!私はコアC++のみを使用しているので、ありがとうとplz no .net lib/code..事前に感謝します

しかし、配列ベースのバージョンが必要です（厳密には..）他の実装を使用することは想定されていません。

4

1 に答える 1

1

ダイクストラ

これがダイクストラの仕組み
です。単純なアルゴリズムではありません。したがって、このアルゴリズムを独自のコードにマップする必要があります。
しかし、頑張ってください。

List<Nodes>    found;     // All processed nodes;
List<Nodes>    front;     // All nodes that have been reached (but not processed)
                          // This list is sorted by the cost of getting to this node.
List<Nodes>    remaining; // All nodes that have not been explored.

remaining.remove(startNode);
front.add(startNode);
startNode.setCost(0); // Cost nothing to get to start.

while(!front.empty())
{
    Node       current = front.getFirstNode();
    front.remove(current);
    found.add(current);

    if (current == endNode)
    {    return current.cost(); // we found the end
    }

    List<Edge> edges   = current.getEdges();

    for(loop = edges.begin(); loop != edges.end(); ++loop)
    {
        Node   dst = edge.getDst();
        if (found.find(dst) != found.end())
        {   continue; // If we have already processed this node ignore it.
        }


        // The cost to get here. Is the cost to get to the last node.
        // Plus the cost to traverse the edge.
        int    cost = current.cost() + loop.cost();
        Node   f    = front.find(dst);
        if (f != front.end())
        {
            f.setCost(std::min(f.cost(), cost));
            continue;  // If the node is on the front line just update the cost
                       // Then continue with the next node.
        }

        // Its a new node.
        // remove it from the remaining and add it to the front (setting the cost).
        remaining.remove(dst);
        front.add(dst);
        dst.setCost(cost);
    }
}
于 2010-09-22T02:20:31.963 に答える