或许在生活中，经常会碰到针对某一个问题，在众多的限制条件下，如何去寻找一个最优解？可能大家想到了很多诸如 “线性规划”，“动态规划”
这些经典策略，当然有的问题我们可以用贪心来寻求整体最优解，在图论中一个典型的贪心法求最优解的例子就莫过于 “最短路径” 的问题。
一：概序
从下图中我要寻找V0到V3的最短路径，你会发现通往他们的两点路径有很多：V0->V4->V3，V0->V1->V3，当然你会认为前者是你要找的最短
路径，那如果说图的顶点非常多，你还会这么轻易的找到吗？下面我们就要将刚才我们那点贪心的思维系统的整理下。
二：构建
如果大家已经了解 Prim 演算法，那么 Dijkstra 演算法只是在它的上面延伸了下，其实也是很简单的。
1. 边节点
这里有点不一样的地方就是我在边上面定义一个 vertexs 来记录贪心搜寻到某一个节点时曾经走过的节点，比如从 V0 贪心搜寻到 V3 时，我们 V3
的 vertexs 可能存放著 V0,V4,V3 这些曾今走过的节点，或许最后这三个节点就是我们要寻找的最短路径。
1 #region 边的资讯
2 ///
4 ///
5 public class Edge
6 {
7 //开始边
8 public int startEdge;
9
10 //结束边
11 public int endEdge;
12
13 //权重
14 public int weight;
15
16 //是否使用
17 public bool isUse;
18
19 //累计顶点
20 public HashSet
21 }
22 #endregion
2.Dijkstra 演算法
首先我们分析下 Dijkstra 演算法的步骤：
有集合 M={V0,V1,V2,V3,V4} 这样 5 个元素，我们用
TempVertex 表示该顶点是否使用。
Weight 表示该 Path 的权重 (预设都为 MaxValue) 。
Path 表示该顶点的总权重。
①. 从集合 M 中挑选顶点 V0 为起始点。给 V0 的所有邻接点赋值，要赋值的前提是要赋值的 weight 要小于原始的 weight，并且排除已经访问过
的顶点，然后挑选当前最小的 weight 作为下一次贪心搜寻的起点，就这样 V0V1 为挑选为最短路径，如图 2 。
②. 我们继续从 V1 这个顶点开始给邻接点以同样的方式赋值，最后我们发现 V0V4 为最短路径。也就是图 3 。
。。。
③. 最后所有顶点的最短路径就这样求出来了 。
1 #region Dijkstra 演算法
2 ///
4 ///
5 public Dictionary
6 {
7 //收集顶点的相邻边
8 Dictionary
9
10 //weight=MaxValue: 标识没有边
11 for (int i = 0; i < graph.vertexsNum; i++)
12 {
13 //起始边
14 var startEdge = i;
15
16 dic_edges.Add(startEdge, new Edge() { weight = int.MaxValue });
17 }
18
19 //取第一个顶点
20 var start = 0;
21
22 for (int i = 0; i < graph.vertexsNum; i++)
23 {
24 //标记该顶点已经使用过
25 dic_edges[start].isUse = true;
26
27 for (int j = 1; j < graph.vertexsNum; j++)
28 {
29 var end = j;
30
31 //取到相邻边的权重
32 var weight = graph.edges[start, end];
33
34 //赋较小的权重
35 if (weight < dic_edges[end].weight)
36 {
37 //与上一个顶点的权值累加
38 var totalweight = dic_edges[start].weight == int.MaxValue ? weight : dic_edges[start].weight + weight;
39
40 if (totalweight < dic_edges[end].weight)
41 {
42 //将该顶点的相邻边加入到集合中
43 dic_edges[end] = new Edge()
44 {
45 startEdge = start,
46 endEdge = end,
47 weight = totalweight
48 };
49
50 //将上一个边的节点的 vertex 累加
51 dic_edges[end].vertexs = new HashSet
52
53 dic_edges[end].vertexs.Add(start);
54 dic_edges[end].vertexs.Add(end);
55 }
56 }
57 }
58
59 var min = int.MaxValue;
60
61 //下一个进行比较的顶点
62 int minkey = 0;
63
64 //取 start 邻接边中的最小值
65 foreach (var key in dic_edges.Keys)
66 {
67 //取当前 最小的 key(使用过的除外)
68 if (min > dic_edges[key].weight && !dic_edges[key].isUse)
69 {
70 min = dic_edges[key].weight;
71 minkey = key;
72 }
73 }
74
75 //从邻接边的顶点再开始找
76 start = minkey;
77 }
78
79 return dic_edges;
80 }
81 #endregion
总的程式码：复杂度很烂 O(N2) 。。。
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading;
using System.IO;
using System.Threading.Tasks;
namespace ConsoleApplication2
{
public class Program
{
public static void Main()
{
Dictionary
MatrixGraph graph = new MatrixGraph();
graph.Build();
var result = graph.Dijkstra();
Console.WriteLine(“ 各节点的最短路径为:”);
foreach (var key in result.Keys)
{
Console.WriteLine(“{0}”, string.Join(“->”, result[key].vertexs));
}
Console.Read();
}
}
#region 定义矩阵节点
///
///
public class MatrixGraph
{
Graph graph = new Graph();
public class Graph
{
///
///
public int[] vertexs;
///
///
public int[,] edges;
///
///
public int vertexsNum;
///
///
public int edgesNum;
}
#region 矩阵的构建
///
///
public void Build()
{
//顶点数
graph.vertexsNum = 5;
//边数
graph.edgesNum = 6;
graph.vertexs = new int[graph.vertexsNum];
graph.edges = new int[graph.vertexsNum, graph.vertexsNum];
//构建二维阵列
for (int i = 0; i < graph.vertexsNum; i++)
{
//顶点
graph.vertexs[i] = i;
for (int j = 0; j < graph.vertexsNum; j++)
{
graph.edges[i, j] = int.MaxValue;
}
}
//定义 6 条边
graph.edges[0, 1] = graph.edges[1, 0] = 2;
graph.edges[0, 2] = graph.edges[2, 0] = 5;
graph.edges[0, 4] = graph.edges[4, 0] = 3;
graph.edges[1, 3] = graph.edges[3, 1] = 4;
graph.edges[2, 4] = graph.edges[4, 2] = 5;
graph.edges[3, 4] = graph.edges[4, 3] = 2;
}
#endregion
#region 边的资讯
///
///
public class Edge
{
//开始边
public int startEdge;
//结束边
public int endEdge;
//权重
public int weight;
//是否使用
public bool isUse;
//累计顶点
public HashSet
}
#endregion
#region Dijkstra 演算法
///
///
public Dictionary
{
//收集顶点的相邻边
Dictionary
//weight=MaxValue: 标识没有边
for (int i = 0; i < graph.vertexsNum; i++)
{
//起始边
var startEdge = i;
dic_edges.Add(startEdge, new Edge() { weight = int.MaxValue });
}
//取第一个顶点
var start = 0;
for (int i = 0; i < graph.vertexsNum; i++)
{
//标记该顶点已经使用过
dic_edges[start].isUse = true;
for (int j = 1; j < graph.vertexsNum; j++)
{
var end = j;
//取到相邻边的权重
var weight = graph.edges[start, end];
//赋较小的权重
if (weight < dic_edges[end].weight)
{
//与上一个顶点的权值累加
var totalweight = dic_edges[start].weight == int.MaxValue ? weight : dic_edges[start].weight + weight;
if (totalweight < dic_edges[end].weight)
{
//将该顶点的相邻边加入到集合中
dic_edges[end] = new Edge()
{
startEdge = start,
endEdge = end,
weight = totalweight
};
//将上一个边的节点的 vertex 累加
dic_edges[end].vertexs = new HashSet
dic_edges[end].vertexs.Add(start);
dic_edges[end].vertexs.Add(end);
}
}
}
var min = int.MaxValue;
//下一个进行比较的顶点
int minkey = 0;
//取 start 邻接边中的最小值
foreach (var key in dic_edges.Keys)
{
//取当前 最小的 key(使用过的除外)
if (min > dic_edges[key].weight && !dic_edges[key].isUse)
{
min = dic_edges[key].weight;
minkey = key;
}
}
//从邻接边的顶点再开始找
start = minkey;
}
return dic_edges;
}
#endregion
}
#endregion
}
文章来自互联网博客网站：http://www.cnblogs.com/huangxincheng/archive/2012/12/18/2823042.html，版权归作者所有。