c++ 最短路兩種算法，短路兩種算法
最短路是個老問題了，大神們留下很多文檔但是很多都是針對算法使用一些固定大小的數組進行數據存儲在實際應用中受到限制，這裡自己練習一下，主要用了一些c++的stl，減少了固定長度數組的依賴，換一種寫法試圖提高可讀性。有興趣的同學可以試著將map/set 換成 hash_set/hash_map 應該能獲得更高的效率，對於稀疏表，內存還是能省不少的。
參考文獻： http://www.cnblogs.com/hxsyl/p/3270401.html
1 /************************************************************************/
2 /* 盡量用簡單快速好理解的方法完成圖的最短路徑 */
3 /************************************************************************/
4 #include <stdio.h>
5 #include <string.h>
6 #include <malloc.h>
7
8 #include <iostream>
9 #include <sstream>
10 #include <string>
11
12 #include <set>
13 #include <map>
14 #include <vector>
15 #include <queue>
16
17 #include <algorithm>
18
19 using namespace std;
20
21 typedef size_t Index;
22
23 // 使用整數比string快
24 map<string, Index> g_mapNode; // string -> index
25 map<Index, string> g_mapNodeIndex; // index -> string
26 map<Index, set<Index> > g_mapLink; // 鄰接表
27
28 inline bool IsNullString(const char* pcName)
29 {
30 return (NULL == pcName) && ('\0' == pcName[0]);
31 }
32
33 inline bool IsNodeExist(const string& strName)
34 {
35 return g_mapNode.end() != g_mapNode.find(strName);
36 }
37
38 bool FindPath1(Index uSource, Index uTarget, vector<Index>& vecRlst)
39 {
40 map<Index, size_t> mapDistence;
41 map<Index, Index> mapPath;
42
43 // inistalize
44 map<Index, set<Index> >::iterator iterInit = g_mapLink.begin();
45 for (; iterInit != g_mapLink.end(); ++iterInit)
46 {
47 if (iterInit->second.count(uTarget) != 0)
48 {
49 mapDistence[iterInit->first] = 1;
50 mapPath[iterInit->first] = uTarget;
51 }
52 }
53
54 // find
55 size_t uNodeNum = g_mapNode.size();
56 for (size_t i = 0; i < uNodeNum; ++i)
57 {
58 for (size_t j = 0; j < uNodeNum; ++j)
59 {
60 if (g_mapLink.count(i) != 0 && g_mapLink[i].count(j) != 0) // i - > j 是通的
61 {
62 if (mapDistence.count(j) != 0 // j -> uTarget是通的
63 && (mapDistence.count(i) == 0 // i -> uTarget 不存在或者 比從 j走遠
64 || (mapDistence[j] + 1 < mapDistence[i])))
65 {
66 mapDistence[i] = mapDistence[j] + 1; // 更新距離
67 mapPath[i] = j; // 更新下一跳地址
68 }
69 }
70 }
71 }
72
73 // 不可到達
74 if (mapDistence.count(uSource) == 0)
75 {
76 return false;
77 }
78
79 while (uSource != uTarget)
80 {
81 vecRlst.push_back(uSource);
82 uSource = mapPath[uSource];
83 }
84 vecRlst.push_back(uSource);
85
86 return true;
87 }
88
89 bool FindPath2(Index uSource, Index uTarget, vector<Index>& vecRlst)
90 {
91 map<Index, Index> mapLastJump;
92 queue<Index> queNodeQue;
93
94 bool bIsFind = false;
95 queNodeQue.push(uSource);
96 while (!queNodeQue.empty() && !bIsFind)
97 {
98 Index uIdx = queNodeQue.front();
99 queNodeQue.pop();
100 if (g_mapLink.count(uIdx) == 0)
101 {
102 continue;
103 }
104
105 set<Index>::iterator iter = g_mapLink[uIdx].begin();
106 for (; iter != g_mapLink[uIdx].end(); iter++)
107 {
108 if (mapLastJump.count(*iter) != 0)
109 {
110 continue;
111 }
112
113 mapLastJump[*iter] = uIdx;
114 if (*iter == uTarget)
115 {
116 bIsFind = true;
117 break;
118 }
119 queNodeQue.push(*iter);
120 }
121 }
122
123 if (!bIsFind)
124 {
125 return false;
126 }
127
128 while(uTarget != uSource)
129 {
130 vecRlst.push_back(uTarget);
131 uTarget = mapLastJump[uTarget];
132 }
133 vecRlst.push_back(uSource);
134
135 reverse(vecRlst.begin(), vecRlst.end());
136
137 return true;
138 }
139
140 void cmdInitialize()
141 {
142 g_mapNode.clear();
143 g_mapLink.clear();
144 }
145
146 bool cmdAddNode(const char *pcNode)
147 {
148 if (IsNullString(pcNode))
149 {
150 return false;
151 }
152
153 string strName(pcNode);
154 if (IsNodeExist(strName))
155 {
156 return false;
157 }
158
159 Index uIndex = g_mapNode.size();
160 g_mapNode[strName] = uIndex;
161 g_mapNodeIndex[uIndex] = strName;
162
163 return true;
164 }
165
166 bool cmdAddLink(const char *pcSource, const char *pcTarget)
167 {
168 if (IsNullString(pcSource) || IsNullString(pcTarget))
169 {
170 return false;
171 }
172
173 string strSource(pcSource);
174 string strTarget(pcTarget);
175
176 if (!IsNodeExist(strSource) || !IsNodeExist(strTarget) || strSource == strTarget)
177 {
178 return false;
179 }
180
181 g_mapLink[g_mapNode[strSource]].insert(g_mapNode[strTarget]);
182 g_mapLink[g_mapNode[strTarget]].insert(g_mapNode[strSource]);
183
184 return true;
185 }
186
187 bool cmdFindPath(const char *pcSource, const char *pcTarget, char **ppcRlstPath)
188 {
189 if (NULL == ppcRlstPath)
190 {
191 return false;
192 }
193 *ppcRlstPath = NULL;
194
195 string strSource(pcSource);
196 string strTarget(pcTarget);
197
198 if (!IsNodeExist(strSource) || !IsNodeExist(strTarget) || strSource == strTarget)
199 {
200 return false;
201 }
202
203 vector<Index> vecPath;
204 //if(!FindPath1(g_mapNode[strSource], g_mapNode[strTarget], vecPath))
205 if(!FindPath2(g_mapNode[strSource], g_mapNode[strTarget], vecPath))
206 {
207 return false;
208 }
209
210 string strOutPut;
211 stringstream ssOutPut("");
212 for (size_t u = 0; u < vecPath.size(); ++u)
213 {
214 ssOutPut << g_mapNodeIndex[vecPath[u]] << "->";
215 }
216
217 strOutPut = ssOutPut.str();
218 strOutPut = strOutPut.substr(0, strOutPut.length() - 2);
219
220 *ppcRlstPath = (char *)malloc(sizeof(char) * (strOutPut.length() + 1));
221 if (NULL == *ppcRlstPath)
222 {
223 return false;
224 }
225
226 strcpy(*ppcRlstPath, strOutPut.c_str());
227
228 return true;
229 }
230
231 int main()
232 {
233 cmdInitialize();
234
235 cmdAddNode("A");
236 cmdAddNode("B");
237 cmdAddNode("C");
238 cmdAddNode("D");
239
240 cmdAddLink("A", "B");
241 cmdAddLink("B", "C");
242 cmdAddLink("C", "D");
243 cmdAddLink("B", "D");
244
245 char *pcPath = NULL;
246 if (cmdFindPath("A", "D", &pcPath))
247 {
248 printf("%s\n", pcPath);
249 free(pcPath);
250 pcPath = NULL;
251 }
252
253 return 0;
254 }
