最短路是个老问题了，大神们留下很多文档但是很多都是针对算法使用一些固定大小的数组进行数据存储在实际应用中受到限制，这里自己练习一下，主要用了一些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[]);
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) != )
48 {
49 mapDistence[iterInit->first] = ;
50 mapPath[iterInit->first] = uTarget;
51 }
52 }
53
54 // find
55 size_t uNodeNum = g_mapNode.size();
56 for (size_t i = ; i < uNodeNum; ++i)
57 {
58 for (size_t j = ; j < uNodeNum; ++j)
59 {
60 if (g_mapLink.count(i) != && g_mapLink[i].count(j) != ) // i - > j 是通的
61 {
62 if (mapDistence.count(j) != // j -> uTarget是通的
63 && (mapDistence.count(i) == // i -> uTarget 不存在或者 比从 j走远
64 || (mapDistence[j] + < mapDistence[i])))
65 {
66 mapDistence[i] = mapDistence[j] + ; // 更新距离
67 mapPath[i] = j; // 更新下一跳地址
68 }
69 }
70 }
71 }
72
73 // 不可到达
74 if (mapDistence.count(uSource) == )
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();
if (g_mapLink.count(uIdx) == )
{
continue;
}
set<Index>::iterator iter = g_mapLink[uIdx].begin();
for (; iter != g_mapLink[uIdx].end(); iter++)
{
if (mapLastJump.count(*iter) != )
{
continue;
}
mapLastJump[*iter] = uIdx;
if (*iter == uTarget)
{
bIsFind = true;
break;
}
queNodeQue.push(*iter);
}
}
if (!bIsFind)
{
return false;
}
while(uTarget != uSource)
{
vecRlst.push_back(uTarget);
uTarget = mapLastJump[uTarget];
}
vecRlst.push_back(uSource);
reverse(vecRlst.begin(), vecRlst.end());
return true;
}
void cmdInitialize()
{
g_mapNode.clear();
g_mapLink.clear();
}
bool cmdAddNode(const char *pcNode)
{
if (IsNullString(pcNode))
{
return false;
}
string strName(pcNode);
if (IsNodeExist(strName))
{
return false;
}
Index uIndex = g_mapNode.size();
g_mapNode[strName] = uIndex;
g_mapNodeIndex[uIndex] = strName;
return true;
}
bool cmdAddLink(const char *pcSource, const char *pcTarget)
{
if (IsNullString(pcSource) || IsNullString(pcTarget))
{
return false;
}
string strSource(pcSource);
string strTarget(pcTarget);
if (!IsNodeExist(strSource) || !IsNodeExist(strTarget) || strSource == strTarget)
{
return false;
}
g_mapLink[g_mapNode[strSource]].insert(g_mapNode[strTarget]);
g_mapLink[g_mapNode[strTarget]].insert(g_mapNode[strSource]);
return true;
}
bool cmdFindPath(const char *pcSource, const char *pcTarget, char **ppcRlstPath)
{
if (NULL == ppcRlstPath)
{
return false;
}
*ppcRlstPath = NULL;
string strSource(pcSource);
string strTarget(pcTarget);
if (!IsNodeExist(strSource) || !IsNodeExist(strTarget) || strSource == strTarget)
{
return false;
}
vector<Index> vecPath;
//if(!FindPath1(g_mapNode[strSource], g_mapNode[strTarget], vecPath))
if(!FindPath2(g_mapNode[strSource], g_mapNode[strTarget], vecPath))
{
return false;
}
string strOutPut;
stringstream ssOutPut("");
for (size_t u = ; u < vecPath.size(); ++u)
{
ssOutPut << g_mapNodeIndex[vecPath[u]] << "->";
}
strOutPut = ssOutPut.str();
strOutPut = strOutPut.substr(, strOutPut.length() - );
*ppcRlstPath = (char *)malloc(sizeof(char) * (strOutPut.length() + ));
if (NULL == *ppcRlstPath)
{
return false;
}
strcpy(*ppcRlstPath, strOutPut.c_str());
return true;
}
int main()
{
cmdInitialize();
cmdAddNode("A");
cmdAddNode("B");
cmdAddNode("C");
cmdAddNode("D");
cmdAddLink("A", "B");
cmdAddLink("B", "C");
cmdAddLink("C", "D");
cmdAddLink("B", "D");
char *pcPath = NULL;
if (cmdFindPath("A", "D", &pcPath))
{
printf("%s\n", pcPath);
free(pcPath);
pcPath = NULL;
}
return ;
254 }