0

我正在尝试实现一个dijkstra的模型来寻找连接图的最短路径。我所拥有的是一个图表，点击按钮后，它会在图表上随机生成节点。

我想做的是以下几点：

  1. 判断图是否连通
  2. 如果已连接，则选择三种不同方法中的一种来找到最短路径： a. 起点和终点之间距离的最短路径 b. 按边数计算的最短路径 c. 边总权重的最短路径（在这里，我们想要的是更小的权重......）

其他一些注意事项。

因为这些数据点是在这个图表控件中随机生成的，所以我实际上没有 Vertex 类来生成顶点。我一直在四处寻找，发现大多数寻路功能都使用顶点类。所以基本上我的列表将从图表控件之外的节点中填充。

任何人都可以就我如何解决上述两个问题提供任何见解吗？

    //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

计算科学图与我们在统计或数学中制作的“图表”图不同。计算机科学中的图是通过一系列“边”连接的“节点”的集合

一个节点是通过一条边连接的，但这并不意味着它是连接回来的。一些边可以是单向连接。

边缘通常具有与之相关的“权重”或“成本”。这就是您的 dijkstra 算法将派上用场的地方。它将使用此成本来计算到目标的最短路径。

让我们看看我们可能使用的一些数据类型

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 回答