程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> c++ 最短路兩種算法,短路兩種算法

c++ 最短路兩種算法,短路兩種算法

編輯:C++入門知識

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 } 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved