0

接続されたグラフの最短経路を見つけるダイクストラ モデルを実装しようとしています。私が持っているのは、ボタンを押すと、グラフ上にランダムにノードを生成するグラフです。

私がやりたいことは次のとおりです。

  1. グラフが接続されているかどうかを判断する
  2. 接続されている場合、最短パスを見つける 3 つの異なる方法のいずれかを決定します。開始ノードと終了ノード間の距離による最短経路 b. エッジ数による最短経路 c.エッジの総重みによる最短経路 (ここでは、より少ない重みが必要です...)

その他のメモ。

これらの DataPoints はこの chartcontrol でランダムに生成されるため、頂点を生成するための Vertex クラスは実際にはありません。私は周りを検索しており、ほとんどのパス検索関数が頂点クラスを利用していることを確認しています。したがって、基本的に私のリストは、チャート コントロールから離れたノードから取り込まれます。

上記の2つの質問を解決する方法について、誰かが何らかの洞察を提供できますか?

    //TODO:  Change to a function with return bool.  Void for purposes of testing at the moment.
    public void isConnected()
    {

        List<DataPoint> ParentPoints = new List<DataPoint>();

        //Gather all the non data generator into the same point array
        foreach (DataPoint pNonDG in chtGraph.Series[0].Points)
        {
            ParentPoints.Add(pNonDG);
        }
    }
4

1 に答える 1

0

コンピューティング サイエンス グラフは、統計や数学で作成した「チャート」グラフと同じではありません。コンピュータ サイエンスにおけるグラフとは、一連の「エッジ」を介して接続された「ノード」の集合です。

ノードはエッジを介して接続されていますが、それは接続されているという意味ではありません。一部のエッジは一方向接続になる場合があります。

多くの場合、エッジには「重み」または「コスト」が関連付けられています。ここで、ダイクストラのアルゴリズムが役に立ちます。このコストを使用して、ターゲットへの最短パスを計算します。

採用する可能性のあるデータ型のいくつかを見てみましょう

class GraphNode {
    List<GraphEdge> Edges = new List<GraphEdge>();
    public void AddEdge(GraphEdge edge) {
        Edges.Add(edge);
    }
    //you get the idea, this should have much more
    //it also manages edge connections
}

class GraphEdge { //this is a one way connection
    GraphNode ConnectedTo = null;
    //GraphNode ConnectedFrom = null; //if you uncomment this, it can be a two-way
                                      //connection, but you will need more code to
                                      //manage it
    float Cost = 0f;
    //you might consider adding a destructor that clears the pointers
    //otherwise gc might have a hard time getting rid of the nodes
}

class Graph {
    List<GraphNodes> Nodes = new List<GraphNodes>();
    //this class manages the nodes
    //it also provides help for connecting nodes
}
于 2012-10-09T19:35:48.113 に答える