我参考最短路径网页的代码实现寻找最短路径。
请问,如何将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;