或許在生活中，經常會碰到針對某一個問題，在眾多的限制條件下，如何去尋找一個最優解？可能大家想到了很多諸如 “線性規劃”，“動態規劃”
這些經典策略，當然有的問題我們可以用貪心來尋求整體最優解，在圖論中一個典型的貪心法求最優解的例子就莫過於 “最短路徑” 的問題。
一：概序
從下圖中我要尋找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，版權歸作者所有。