2 lu van Lu_van 于 2016.04.14 17:14 提问

C# 最短路径问题,取出最短路径Node编号

我参考最短路径网页的代码实现寻找最短路径。

请问,如何将result中的passNodeID取出来并赋值到新数组?
谢谢大家!!

代码如下

public class Edge
{
    public string StartNodeID;
    public string EndNodeID;
    public double Weight; //权值,代价        
}

public class Node
{
    private string iD;
    private ArrayList edgeList;//Edge的集合--出边表

    public Node(string id)
    {
        this.iD = id;
        this.edgeList = new ArrayList();
    }

    #region property
    public string ID
    {
        get
        {
            return this.iD;
        }
    }

    public ArrayList EdgeList
    {
        get
        {
            return this.edgeList;
        }
    }
    #endregion
}

/// <summary>
/// PassedPath 用于缓存计算过程中的到达某个节点的权值最小的路径
/// </summary>
public class PassedPath
{
    private string curNodeID;
    private bool beProcessed;   //是否已被处理
    private double weight;        //累积的权值
    private ArrayList passedIDList; //路径

    public PassedPath(string ID)
    {
        this.curNodeID = ID;
        this.weight = double.MaxValue;
        this.passedIDList = new ArrayList();
        this.beProcessed = false;
    }

    #region property
    public bool BeProcessed
    {
        get
        {
            return this.beProcessed;
        }
        set
        {
            this.beProcessed = value;
        }
    }

    public string CurNodeID
    {
        get
        {
            return this.curNodeID;
        }
    }

    public double Weight
    {
        get
        {
            return this.weight;
        }
        set
        {
            this.weight = value;
        }
    }

    public ArrayList PassedIDList
    {
        get
        {
            return this.passedIDList;
        }
    }
    #endregion
}

/// <summary>
/// PlanCourse 缓存从源节点到其它任一节点的最小权值路径=》路径表
/// </summary>
public class PlanCourse
{
    private Hashtable htPassedPath;

    #region ctor
    public PlanCourse(ArrayList nodeList, string originID)
    {
        this.htPassedPath = new Hashtable();

        Node originNode = null;
        foreach (Node node in nodeList)
        {
            if (node.ID == originID)
            {
                originNode = node;
            }
            else
            {
                PassedPath pPath = new PassedPath(node.ID);
                this.htPassedPath.Add(node.ID, pPath);
            }
        }

        if (originNode == null)
        {
            throw new Exception("The origin node is not exist !");
        }

        this.InitializeWeight(originNode);
    }

    private void InitializeWeight(Node originNode)
    {
        if ((originNode.EdgeList == null) || (originNode.EdgeList.Count == 0))
        {
            return;
        }

        foreach (Edge edge in originNode.EdgeList)
        {
            PassedPath pPath = this[edge.EndNodeID];
            if (pPath == null)
            {
                continue;
            }

            pPath.PassedIDList.Add(originNode.ID);
            pPath.Weight = edge.Weight;
        }
    }
    #endregion

    public PassedPath this[string nodeID]
    {
        get
        {
            return (PassedPath)this.htPassedPath[nodeID];
        }
    }
}

public class RoutePlanResult
{
    public string[] passNodeID;  //通过的点的ID
    public double pPathWeirht;  //路径的权值
    public RoutePlanResult(string[] passID, double weight)
    {
        passNodeID = passID;
        pPathWeirht = weight;
    }
}

/// <summary>
/// RoutePlanner 提供图算法中常用的路径规划功能。
/// 2005.09.06
/// </summary>
public class RoutePlanner
{
    public RoutePlanner()
    {
    }

    #region Paln
    //获取权值最小的路径
    public RoutePlanResult Paln(ArrayList nodeList, string originID, string destID)
    {
        PlanCourse planCourse = new PlanCourse(nodeList, originID);

        Node curNode = this.GetMinWeightRudeNode(planCourse, nodeList, originID);

        #region 计算过程
        while (curNode != null)
        {
            PassedPath curPath = planCourse[curNode.ID];
            foreach (Edge edge in curNode.EdgeList)
            {
                if (edge.EndNodeID == originID)
                    continue;

                PassedPath targetPath = planCourse[edge.EndNodeID];
                double tempWeight = curPath.Weight + edge.Weight;

                if (tempWeight < targetPath.Weight)
                {
                    targetPath.Weight = tempWeight;
                    targetPath.PassedIDList.Clear();

                    for (int i = 0; i < curPath.PassedIDList.Count; i++)
                    {
                        targetPath.PassedIDList.Add(curPath.PassedIDList[i].ToString());
                    }

                    targetPath.PassedIDList.Add(curNode.ID);
                }
            }

            //标志为已处理
            planCourse[curNode.ID].BeProcessed = true;
            //获取下一个未处理节点
            curNode = this.GetMinWeightRudeNode(planCourse, nodeList, originID);
        }
        #endregion

        //表示规划结束
        return this.GetResult(planCourse, destID);
    }
    #endregion

    #region private method
    #region GetResult
    //从PlanCourse表中取出目标节点的PassedPath,这个PassedPath即是规划结果
    private RoutePlanResult GetResult(PlanCourse planCourse, string destID)
    {
        PassedPath pPath = planCourse[destID];

        if (pPath.Weight == int.MaxValue)
        {
            RoutePlanResult result1 = new RoutePlanResult(null, int.MaxValue);
            return result1;
        }

        string[] passedNodeIDs = new string[pPath.PassedIDList.Count];
        for (int i = 0; i < passedNodeIDs.Length; i++)
        {
            passedNodeIDs[i] = pPath.PassedIDList[i].ToString();
        }
        RoutePlanResult result = new RoutePlanResult(passedNodeIDs, pPath.Weight);

        return result;
    }
    #endregion

    #region GetMinWeightRudeNode
    //从PlanCourse取出一个当前累积权值最小,并且没有被处理过的节点
    private Node GetMinWeightRudeNode(PlanCourse planCourse, ArrayList nodeList, string originID)
    {
        double weight = double.MaxValue;
        Node destNode = null;

        foreach (Node node in nodeList)
        {
            if (node.ID == originID)
            {
                continue;
            }

            PassedPath pPath = planCourse[node.ID];
            if (pPath.BeProcessed)
            {
                continue;
            }

            if (pPath.Weight < weight)
            {
                weight = pPath.Weight;
                destNode = node;
            }
        }

        return destNode;
    }
    #endregion
    #endregion
}

//[STAThread]
static void Main(string[] args)
{
    ArrayList nodeList = new ArrayList();

    //***************** A Node *******************
    Node aNode = new Node("A");
    nodeList.Add(aNode);
    //A -> B
    Edge aEdge1 = new Edge();
    aEdge1.StartNodeID = aNode.ID;
    aEdge1.EndNodeID = "B";
    aEdge1.Weight = 10;
    aNode.EdgeList.Add(aEdge1);
    //A -> C
    Edge aEdge2 = new Edge();
    aEdge2.StartNodeID = aNode.ID;
    aEdge2.EndNodeID = "C";
    aEdge2.Weight = 20;
    aNode.EdgeList.Add(aEdge2);
    //A -> E
    Edge aEdge3 = new Edge();
    aEdge3.StartNodeID = aNode.ID;
    aEdge3.EndNodeID = "E";
    aEdge3.Weight = 30;
    aNode.EdgeList.Add(aEdge3);

    //***************** B Node *******************
    Node bNode = new Node("B");
    nodeList.Add(bNode);
    //B -> C
    Edge bEdge1 = new Edge();
    bEdge1.StartNodeID = bNode.ID;
    bEdge1.EndNodeID = "C";
    bEdge1.Weight = 5;
    bNode.EdgeList.Add(bEdge1);
    //B -> E
    Edge bEdge2 = new Edge();
    bEdge2.StartNodeID = bNode.ID;
    bEdge2.EndNodeID = "E";
    bEdge2.Weight = 10;
    bNode.EdgeList.Add(bEdge2);

    //***************** C Node *******************
    Node cNode = new Node("C");
    nodeList.Add(cNode);
    //C -> D
    Edge cEdge1 = new Edge();
    cEdge1.StartNodeID = cNode.ID;
    cEdge1.EndNodeID = "D";
    cEdge1.Weight = 30;
    cNode.EdgeList.Add(cEdge1);

    //***************** D Node *******************
    Node dNode = new Node("D");
    nodeList.Add(dNode);

    //***************** E Node *******************
    Node eNode = new Node("E");
    nodeList.Add(eNode);
    //C -> D
    Edge eEdge1 = new Edge();
    eEdge1.StartNodeID = eNode.ID;
    eEdge1.EndNodeID = "D";
    eEdge1.Weight = 20;
    eNode.EdgeList.Add(eEdge1);


    RoutePlanner planner = new RoutePlanner();
    RoutePlanResult result = planner.Paln(nodeList, "A", "D");

    planner = null;

3个回答

caozhy
caozhy   Ds   Rxr 2016.04.14 22:58

string[] newarr = result.passNodeID.ToArray();

Lu_van
Lu_van 好的,我试试!谢谢!
一年多之前 回复
caozhy
caozhy   Ds   Rxr 2016.04.14 22:58

string[] new arr = result.passNodeID;

Lu_van
Lu_van   2016.04.15 14:25

string[] node = new string[passednode.ResultNodes.Length];
node = passednode.ResultNodes.ToArray();//node数组中储存着除终点之外的所有点


这是我最后采用的代码

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!