首先新建一个网图如下：
图的表示法有好多中，最常用的应该是邻接矩阵与邻接表。上面的图，边很少，用邻接表来表示就很不错。
对于以上图，可以对象出3个类。图、节点、边。3个实体类代码如下：
边Edge：
public class Edge
{
public string StartNodeID
{
get;
set;
}
public string EndNodeID
{
get;
set;
}
public int Weight
{
get;
set;
}
}
节点Node：
public class Node
{
private string id;
private IList edgeList;
public Node(string nid)
{
id = nid;
edgeList = new List();
}
public string Id
{
get
{
return id;
}
}
public IList EdgeList
{
get
{
return edgeList;
}
}
}
图Graph：
public class Graph
{
public List NodeList = new List();
}
由于要求的就是最短路径，路径对象模拟如下：
public class Path { public string CurrentNodeId; public bool IsProcessed = false; public int Weight = 99999999; public List<string> PathNodeList = new List<string>(); }
最短路径计算类：
/// /// 计算最短路径帮助类 /// public class CaculateHelper { private Dictionary<string, Path> dicPath = new Dictionary<string, Path>(); public Dictionary<string, Path> DicPath { get { return dicPath; } } public void IniFirstNode(Graph graph, string StartNodeId) { Node OriginNode = null; foreach (Node node in graph.NodeList) { if (node.Id == StartNodeId) { OriginNode = node; } else { Path path = new Path(); path.CurrentNodeId = node.Id; dicPath.Add(path.CurrentNodeId, path); //初始化A->到所有边都是默认的Path 99999999 } } //如果有A直接进入的边，则设置为相应权重值，和记录下路径 foreach (Edge edge in OriginNode.EdgeList) { Path path = new Path(); path.CurrentNodeId = edge.EndNodeID; path.Weight = edge.Weight; path.PathNodeList.Add(edge.StartNodeID); dicPath[path.CurrentNodeId] = path; } } public Node GetFromNodeMinWeightNode(Graph graph) { Node CNode = null; KeyValuePair<string, Path> KVPPath = dicPath.Where(m => !m.Value.IsProcessed).OrderBy(m => m.Value.Weight).FirstOrDefault(); if (KVPPath.Key != null) { CNode = graph.NodeList.FirstOrDefault(m => m.Id == KVPPath.Value.CurrentNodeId); } return CNode; } /// /// 计算最短权值路径 /// public void CatelateMinWeightRoad(Graph graph) { //取从第一个点出发，最小权值且未被访问果的节点的点 Node CNode = GetFromNodeMinWeightNode(graph); //这段代码是核心 循环每个顶点，看看经过该顶点是否会让权值变小，如果会则存起此路径。直到再未访问过的点 while (CNode != null) { Path CurrentPath = dicPath[CNode.Id]; foreach (Edge edge in CNode.EdgeList) { Path TargetPath = dicPath[edge.EndNodeID]; int tempWeight = CurrentPath.Weight + edge.Weight; if (tempWeight < TargetPath.Weight) { TargetPath.Weight = tempWeight; TargetPath.PathNodeList.Clear(); for (int i = 0; i < CurrentPath.PathNodeList.Count; i++) { TargetPath.PathNodeList.Add(CurrentPath.PathNodeList[i].ToString()); } TargetPath.PathNodeList.Add(CNode.Id); } } //标志为已处理 dicPath[CNode.Id].IsProcessed = true; //再次获取权值最小的点 CNode = GetFromNodeMinWeightNode(graph); } } }
主控制台程序：
class Program
{
static void Main(string[] args)
{
Graph graph = new Graph();
#region 初始化一个图的 节点和边
//***************** B Node *******************
Node aNode = new Node("A");
graph.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");
graph.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");
graph.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");
graph.NodeList.Add(dNode);
//***************** C Node *******************
Node eNode = new Node("E");
graph.NodeList.Add(eNode);
//E -> D
Edge eEdge1 = new Edge();
eEdge1.StartNodeID = eNode.Id;
eEdge1.EndNodeID = "D";
eEdge1.Weight = 20;
eNode.EdgeList.Add(eEdge1);
//E -> F
Edge eEdge2 = new Edge();
eEdge2.StartNodeID = eNode.Id;
eEdge2.EndNodeID = "F";
eEdge2.Weight = 20;
eNode.EdgeList.Add(eEdge2);
//***************** F Node *******************
Node fNode = new Node("F");
graph.NodeList.Add(fNode);
#endregion
//计算从A -> C的最短权值路线
string StartNodeId = "A";
string EndNodeId = "F";
CaculateHelper CH = new CaculateHelper();
//第一步，初始化初始化源点 A 到 其他各点的 权重以及 路径(完成 A->B A->C A->E A->D 边权重，与A无直接边的则默认99999999)
CH.IniFirstNode(graph, StartNodeId);
//第二步，从权重最小的点开始，一直到权值最大的点
CH.CatelateMinWeightRoad(graph);
#region 以下与计算无关，仅仅用于将结果打印出来
Path ShowPath = CH.DicPath[EndNodeId];
foreach(string MiddleNodeId in ShowPath.PathNodeList)
{
Console.WriteLine(MiddleNodeId);
}
Console.WriteLine(ShowPath.Weight);
#endregion
Console.ReadKey();
}
}
不要小看上面这几行代码，哥看了好久才看懂，如果Node里加几个坐标，就能在地图上面展示了。下一篇会将它改造成可以在地图上面展示的路径规划。
Original: https://www.cnblogs.com/kissdodog/p/5437897.html
Author: 逆心
Title: 带权重的有向图求最短路径
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/552317/
转载文章受原作者版权保护。转载请注明原作者出处！