c++ 最短路两种算法
2024-04-07 08:54:57
最短路是个老问题了，大神们留下很多文档但是很多都是针对算法使用一些固定大小的数组进行数据存储在实际应用中受到限制，这里自己练习一下，主要用了一些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 }
最新文章
- ruby 访问新浪微博API post方式和get方式
- sql2008 r2 重新启动 失败解决办法
- 一个Eclipse代码显示主题
- 基础4 Android基础
- SQL数据库基本操作语句
- 获取XML数据
- 易pc，1G容量以上的u盘，另外还要一台装了windows系统的电脑。
- C# System.IO.FileStream 文件正由另一进程使用，因此该进程无法访问该文件
- jquery特效 幻灯片效果
- 在阿里云ECS（CentOS6.5）上安装mysql
- MQ的导出备份
- 201521123095 《Java程序设计》第8周学习总结
- 第77节:Java中的事务和数据库连接池和DBUtiles
- centos7安装Lua
- sql server查看用户权限
- vs 编译库文件
- 尚硅谷springboot学习14-自动配置原理
- Font Awesome（一套很棒的图标库）
- html块元素和内联元素
- Java时间操作常用api