- A+
所属分类：Fly数据结构与算法 原创文章
图的最短路径算法，啊？广度优先搜索不就是求最短路径吗？好吧，广度优先搜索是求的最短节点数到达，但是每个节点到每个节点的距离（权重）不一样，就好比东莞到惠州和东莞到北京。所以这时候就要用迪克斯特拉算法了。
一、首先，是点和边
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Vertex {//顶点 public string Name; public Vertex(string name) { Name = name; } } class Edge {//边 public Vertex From; public Vertex To; public int Weight;//权重 public Edge(Vertex from, Vertex to, int weight) { From = from; To = to; Weight = weight; } } |
一个图，可以这样说吧，就是有点（节点），边（节点之间的关系）构成的，这里的边，有一个权重值，就是用来衡量这个边（节点到节点的成本，两地的距离）。下面就用这些来构建一个图。
二、构建权重图（测试用的数据）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Vertex O = new Vertex("O"); Vertex A = new Vertex("A"); Vertex B = new Vertex("B"); Vertex C = new Vertex("c"); //构建权重图 Edge OA = new Edge(O, A, 6); Edge OB = new Edge(O, B, 3); dict.Add("O", new Edge[] { OA, OB }); Edge BA = new Edge(B, A, 2); Edge BC = new Edge(B, C, 9); dict.Add("B", new Edge[] { BA, BC }); Edge AC = new Edge(A, C, 1); dict.Add("A", new Edge[] { AC }); |
这里构建了四个点，还有O到A，O到B，B到A，B到C，A到C，5条边。看图，还有权重值，找出权重值总和最小的路径都参考此图
三、获取目前路径总权重最小的结点数据
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
//获取总权重值最小，又没有被访问过路径 static VisitVertex GetLowVertex(Dictionary<Vertex, VisitVertex> d) { int val = Int32.MaxValue; VisitVertex visit = null; foreach (var i in d) { if (i.Value.IsVisited == false) { if (i.Value.Weight < val) {//新路径比旧路径权重值小 val = i.Value.Weight; visit = i.Value; } } } if (visit != null) { //标志该路径以被访问过 visit.IsVisited = true; } return visit; } |
每步最优解啊，所以遍历路径来找到那个权重最小的路径，已经访问过的就不用再去访问啦，不然可能死循环咯
四、主函数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
static void SearchLow(Vertex x){ Dictionary<Vertex, Vertex> parent = new Dictionary<Vertex, Vertex>();//保存最短节点与节点的关系 Dictionary<Vertex, VisitVertex> weight = new Dictionary<Vertex, VisitVertex>();//记录当前最小权重 //初始化三个字典，起点开始 //获取到起点开始指向的边 Edge[] edges; dict.TryGetValue("O", out edges); foreach (Edge e in edges) { parent.Add(e.To, e.From); weight.Add(e.To, new VisitVertex(e.Weight,false,e.To)); } VisitVertex go = null; while ((go = GetLowVertex(weight)) != null) { Edge[] edges2; dict.TryGetValue(go.Vertex.Name, out edges2); if (edges2 == null) break; foreach (Edge ee in edges2) { int myWeight = go.Weight + ee.Weight; VisitVertex orightWeight; weight.TryGetValue(ee.To, out orightWeight); if (orightWeight == null) { //如果没有过该路径，就添加 weight.Add(ee.To, new VisitVertex(myWeight, false, ee.To)); parent.Add(ee.To, ee.From); } else { if (orightWeight.Weight > myWeight) { //发现更短的路径，更新权重值，更改为没有访问过，修改父节点（新路径了） orightWeight.Weight = myWeight; orightWeight.IsVisited = false; parent[ee.To] = ee.From; } } } } //输出路径和权重总值 VisitVertex finVist; weight.TryGetValue(x, out finVist); Console.WriteLine("总权重值：" + finVist.Weight); Console.WriteLine(x.Name); Vertex cur = x; while (true) { Vertex aaa; parent.TryGetValue(cur, out aaa); cur = aaa; if (aaa == null) { break; } Console.WriteLine(aaa.Name); } } |
这里是主要的功能函数。首先，当然是要从起点开始啦，先初始化字典，就是起点到临近结点的距离（路径），到终点的路径距离是不知道的，所以先设为无穷（这里用Int32的最大值表示）。随后就是一直重复做的事情了。主要思想就是先获取路径中最小权重的路径，访问它的尾结点到其他所有结点的总权重（加起来），再去更新路径（如果有更近的到达方案或者是这个结点没有到达过），记得也要更新父节点字典啊，它主要记录的是最短到达本节点的路径的父节点（上一个节点）。所以，最后的时候就可以通过父节点字典从终点，一直访问父节点得到最短路径了
五、结果
注意：图不能出现环图（2个或两个结点可以绕圈圈到达），也不能出现负权重，权重只是表达该路径的大小长短等价值值，很容易控制，而环图就需要注意了
完整代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 |
class Vertex {//顶点 public string Name; public Vertex(string name) { Name = name; } } class Edge {//边 public Vertex From; public Vertex To; public int Weight; public Edge(Vertex from, Vertex to, int weight) { From = from; To = to; Weight = weight; } } class VisitVertex {//用来记录存在的路径和总权重，简称路径 public int Weight; public bool IsVisited; public Vertex Vertex; public VisitVertex(int weight, bool isVisited,Vertex vertex) { Weight = weight; IsVisited = isVisited; Vertex = vertex; } } class Program { static Dictionary<string, Edge[]> dict = new Dictionary<string, Edge[]>(); static void Main(string[] args) { Vertex O = new Vertex("O"); Vertex A = new Vertex("A"); Vertex B = new Vertex("B"); Vertex C = new Vertex("c"); //构建权重图 Edge OA = new Edge(O, A, 6); Edge OB = new Edge(O, B, 3); dict.Add("O", new Edge[] { OA, OB }); Edge BA = new Edge(B, A, 2); Edge BC = new Edge(B, C, 9); dict.Add("B", new Edge[] { BA, BC }); Edge AC = new Edge(A, C, 1); dict.Add("A", new Edge[] { AC }); SearchLow(C); Console.ReadKey(); } static void SearchLow(Vertex x){ Dictionary<Vertex, Vertex> parent = new Dictionary<Vertex, Vertex>();//保存最短节点与节点的关系 Dictionary<Vertex, VisitVertex> weight = new Dictionary<Vertex, VisitVertex>();//记录当前最小权重 //初始化三个字典，起点开始 //获取到起点开始指向的边 Edge[] edges; dict.TryGetValue("O", out edges); foreach (Edge e in edges) { parent.Add(e.To, e.From); weight.Add(e.To, new VisitVertex(e.Weight,false,e.To)); } VisitVertex go = null; while ((go = GetLowVertex(weight)) != null) { Edge[] edges2; dict.TryGetValue(go.Vertex.Name, out edges2); if (edges2 == null) break; foreach (Edge ee in edges2) { int myWeight = go.Weight + ee.Weight; VisitVertex orightWeight; weight.TryGetValue(ee.To, out orightWeight); if (orightWeight == null) { //如果没有过该路径，就添加 weight.Add(ee.To, new VisitVertex(myWeight, false, ee.To)); parent.Add(ee.To, ee.From); } else { if (orightWeight.Weight > myWeight) { //发现更短的路径，更新权重值，更改为没有访问过，修改父节点（新路径了） orightWeight.Weight = myWeight; orightWeight.IsVisited = false; parent[ee.To] = ee.From; } } } } //输出路径和权重总值 VisitVertex finVist; weight.TryGetValue(x, out finVist); Console.WriteLine("总权重值：" + finVist.Weight); Console.WriteLine(x.Name); Vertex cur = x; while (true) { Vertex aaa; parent.TryGetValue(cur, out aaa); cur = aaa; if (aaa == null) { break; } Console.WriteLine(aaa.Name); } } //获取总权重值最小，又没有被访问过路径 static VisitVertex GetLowVertex(Dictionary<Vertex, VisitVertex> d) { int val = Int32.MaxValue; VisitVertex visit = null; foreach (var i in d) { if (i.Value.IsVisited == false) { if (i.Value.Weight < val) {//新路径比旧路径权重值小 val = i.Value.Weight; visit = i.Value; } } } if (visit != null) { //标志该路径以被访问过 visit.IsVisited = true; } return visit; } } |
