前文讲到了图论中的最小生成树问题，个人觉得有必要继续讲讲最短路径算法的选路问题。
什么是最短路径？
互联网技术和应用的不断发展，对当今网络通信流量的要求不断增大。流量大、速度快、费用低的传输方式是网络传输的关键。路径最短、代价最低的网络路由能够大大降低通信成本、节约网络资源，提高网络资源的利用率。
最短路径问题是组合优化领域的经典问题之一，它广泛应用于计算机科学、交通工程、通信工程、系统工程、运筹学、信息论、控制理论等众多领域。Dijkstra算法是经典的最短路径算法。
狄克斯特拉算法
Dijkstra算法是经典的最短路径算法，其基本思想是：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v, …, vk，就将vk加入集合S中，并将路径v, …, vk , vi与原来的假设相比较，取路径长度较小者为最短路径，重复上述过程，直到集合V中全部顶点加入到集合S中。使用该算法找到的是全局最优的最短路径，在网络节点数量大、网络边数较多时，存在内存占用大、时间复杂度高等不足，并且Dijkstra算法不能很好地解决含必经点约束的最短路径问题。
假设有这样一张图，需要求解从A点到其他点的最短路径：
image.png
一个C++算法实现
拿上面的图做为例子，具体实现下面的代码：
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string>
#include <vector>
#include <set>
#include <map>
// 邻边
struct SEdge
{
std::string strVertexFrom;
std::string strVertexTo;
int nEdgeWeight;
SEdge(const std::string& strFrom = "", const std::string& strTo = "", int nWeight = 0)
{
strVertexFrom = strFrom;
strVertexTo = strTo;
nEdgeWeight = nWeight;
}
};
// 邻接矩阵
class CThroughMatrix
{
// 顶点集合
std::set<std::string> m_setVertex;
// 邻边集合
typedef std::map<std::string, int> MAP_TOVERTEX_WEIGHT_t;
std::map<std::string, MAP_TOVERTEX_WEIGHT_t> m_mapEdge;
public:
CThroughMatrix()
{
}
virtual ~CThroughMatrix()
{
}
// 新增顶点名称
void addVertex(const std::string& strVertex)
{
if (m_setVertex.find(strVertex) == m_setVertex.end())
{
m_setVertex.insert(strVertex);
printf("add vertex:[%s] \n", strVertex.c_str());
}
}
// 移除指定顶点
void delVertex(const std::string& strVertex)
{
if (m_setVertex.find(strVertex) == m_setVertex.end())
return;
// 找该顶点的入度，删除邻边
for (auto iter = m_mapEdge.begin(); iter != m_mapEdge.end(); ++iter)
{
MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = iter->second;
auto iterEdge = mapToVertexWeight.find(strVertex);
if (iterEdge != mapToVertexWeight.end())
{
printf("delete edge:[%s -> %s] weight:[%d] \n", iter->first.c_str(), iterEdge->first.c_str(), iterEdge->second);
mapToVertexWeight.erase(iterEdge);
if (mapToVertexWeight.empty())
{
m_mapEdge.erase(iter);
}
}
}
// 找该顶点的出度，删除邻边
auto iter = m_mapEdge.find(strVertex);
if (iter != m_mapEdge.end())
{
MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = iter->second;
for (auto iterEdge = mapToVertexWeight.begin(); iterEdge != mapToVertexWeight.end(); ++iterEdge)
{
printf("delete edge:[%s -> %s] weight:[%d] \n", iter->first.c_str(), iterEdge->first.c_str(), iterEdge->second);
}
m_mapEdge.erase(iter);
}
// 删除顶点
m_setVertex.erase(strVertex);
}
// 增加邻边
void addEdge(const std::string& strVertex1, const std::string& strVertex2, int nWeight, bool bDirect = false)
{
// 检查顶点是否存在
if (m_setVertex.find(strVertex1) == m_setVertex.end())
return;
if (m_setVertex.find(strVertex2) == m_setVertex.end())
return;
// 添加 strVertex1 -> strVertex2
{
MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = m_mapEdge[strVertex1];
auto iterEdge = mapToVertexWeight.find(strVertex2);
if (iterEdge != mapToVertexWeight.end())
{
iterEdge->second = nWeight;
printf("update edge:[%s -> %s] weight:[%d] \n", strVertex1.c_str(), strVertex2.c_str(), nWeight);
}
else
{
mapToVertexWeight.insert( std::make_pair(strVertex2, nWeight) );
printf("add edge:[%s -> %s] weight:[%d] \n", strVertex1.c_str(), strVertex2.c_str(), nWeight);
}
}
// 无向图添加 strVertex2 -> strVertex1
if (!bDirect)
{
MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = m_mapEdge[strVertex2];
auto iterEdge = mapToVertexWeight.find(strVertex1);
if (iterEdge != mapToVertexWeight.end())
{
iterEdge->second = nWeight;
printf("update edge:[%s -> %s] weight:[%d] \n", strVertex2.c_str(), strVertex1.c_str(), nWeight);
}
else
{
mapToVertexWeight.insert( std::make_pair(strVertex1, nWeight) );
printf("add edge:[%s -> %s] weight:[%d] \n", strVertex2.c_str(), strVertex1.c_str(), nWeight);
}
}
}
// 删除邻边
void delEdge(const std::string& strVertex1, const std::string& strVertex2, bool bDirect = false)
{
// 检查顶点是否存在
if (m_setVertex.find(strVertex1) == m_setVertex.end())
return;
if (m_setVertex.find(strVertex2) == m_setVertex.end())
return;
// 删除 strVertex1 -> strVertex2
{
auto iter = m_mapEdge.find(strVertex1);
if (iter != m_mapEdge.end())
{
MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = iter->second;
auto iterEdge = mapToVertexWeight.find(strVertex2);
if (iterEdge != mapToVertexWeight.end())
{
mapToVertexWeight.erase(iterEdge);
if (mapToVertexWeight.empty())
{
m_mapEdge.erase(strVertex1);
}
printf("delete edge:[%s -> %s] \n", strVertex1.c_str(), strVertex2.c_str());
}
}
}
// 无向图删除 strVertex2 -> strVertex1
if (!bDirect)
{
auto iter = m_mapEdge.find(strVertex2);
if (iter != m_mapEdge.end())
{
MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = iter->second;
auto iterEdge = mapToVertexWeight.find(strVertex1);
if (iterEdge != mapToVertexWeight.end())
{
mapToVertexWeight.erase(iterEdge);
if (mapToVertexWeight.empty())
{
m_mapEdge.erase(strVertex1);
}
printf("delete edge:[%s -> %s] \n", strVertex2.c_str(), strVertex1.c_str());
}
}
}
}
// 使用普里姆算法计算最小生成树
bool calcMinWeightTreeByPrim(std::vector<SEdge>& vecEdge) const
{
if (m_setVertex.empty())
{
printf("no vertex! \n");
return false;
}
std::set<std::string> setVertexLeft, setVertexRight = m_setVertex;
// 初使化左右顶点集合
// 左顶点集合为已探知，右顶点集合为待探知
const std::string& strVertex = *setVertexRight.begin();
setVertexLeft.insert(strVertex);
setVertexRight.erase(strVertex);
while (!setVertexRight.empty())
{
// 寻找从左边顶点到右边顶点的最小邻边
std::string strFrom = "", strTo = "";
int nMinWeight = -1;
for (auto iterLeft = setVertexLeft.begin(); iterLeft != setVertexLeft.end(); ++iterLeft)
{
const std::string& strLeft = (*iterLeft);
auto iter = m_mapEdge.find(strLeft);
if (iter == m_mapEdge.end())
{
printf("vertex:[%s] no edge! \n", strLeft.c_str());
return false;
}
const MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = iter->second;
for (auto iterEdge = mapToVertexWeight.begin(); iterEdge != mapToVertexWeight.end(); ++iterEdge)
{
const std::string& strRight = iterEdge->first;
// 过滤已探知的顶点
if (setVertexRight.find(strRight) == setVertexRight.end())
continue;
if (nMinWeight < 0 || iterEdge->second < nMinWeight)
{
strFrom = strLeft;
strTo = strRight;
nMinWeight = iterEdge->second;
}
}
}
// 找到权重最小的待探知顶点
if (strTo != "")
{
SEdge stEdge(strFrom, strTo, nMinWeight);
vecEdge.push_back(stEdge);
// 将顶点从右边移动到左边
setVertexLeft.insert(strTo);
setVertexRight.erase(strTo);
}
}
return true;
}
// 使用狄克斯特拉算法计算从指定点到其他点的最小距离
bool calcMinDistanceByDijkstra(const std::string& strVertexSrc, std::vector<std::pair<std::string, int> >& vecDistance) const
{
if (m_setVertex.find(strVertexSrc) == m_setVertex.end())
{
printf("no vertex! \n");
return false;
}
// 初使化距离表
std::map<std::string, int> mapDistance;
for (auto iter = m_setVertex.begin(); iter != m_setVertex.end(); ++iter)
{
mapDistance[*iter] = -1;
}
std::set<std::string> setVertexRight = m_setVertex;
// 初使化选择起始顶点
printf("choose vertex:[%s] \n", strVertexSrc.c_str());
vecDistance.push_back(std::make_pair(strVertexSrc, 0));
// 标明起始顶点为已探知
setVertexRight.erase(strVertexSrc);
mapDistance[strVertexSrc] = 0;
printf("update to:[%s] distance:[0] \n", strVertexSrc.c_str());
// 更新与起始顶点直连顶点的距离
{
auto iter = m_mapEdge.find(strVertexSrc);
if (iter == m_mapEdge.end())
{
printf("source vertex:[%s] no edge! \n", strVertexSrc.c_str());
return false;
}
const MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = iter->second;
for (auto iterEdge = mapToVertexWeight.begin(); iterEdge != mapToVertexWeight.end(); ++iterEdge)
{
mapDistance[iterEdge->first] = iterEdge->second;
printf("update to:[%s] distance:[%d] \n", iterEdge->first.c_str(), iterEdge->second);
}
}
while (!setVertexRight.empty())
{
// 从已知探明的顶点中取取距离最小的顶点
std::string strChoose = "";
int nMinDistance = -1;
for (auto iter = mapDistance.begin(); iter != mapDistance.end(); ++iter)
{
// 必须为距离已探明
if (iter->second < 0)
continue;
// 必须为顶点未探明
if (setVertexRight.find(iter->first) == setVertexRight.end())
continue;
if (nMinDistance < 0 || iter->second < nMinDistance)
{
strChoose = iter->first;
nMinDistance = iter->second;
}
}
// 找到最小距离顶点
if (strChoose != "")
{
printf("choose nearest vertex:[%s] distance:[%d] \n", strChoose.c_str(), mapDistance[strChoose]);
vecDistance.push_back(std::make_pair(strChoose, mapDistance[strChoose]));
// 标记该顶点为已探知
setVertexRight.erase(strChoose);
// 更新通过strChoose顶点可达的距离
auto iter = m_mapEdge.find(strChoose);
if (iter == m_mapEdge.end())
{
printf("vertex:[%s] no edge! \n", strChoose.c_str());
continue;
}
const MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = iter->second;
for (auto iterEdge = mapToVertexWeight.begin(); iterEdge != mapToVertexWeight.end(); ++iterEdge)
{
const std::string& strRight = iterEdge->first;
int nWeight = iterEdge->second;
// 过滤已探知的顶点
if (setVertexRight.find(strRight) == setVertexRight.end())
continue;
// 更新相邻顶点的距离
if (mapDistance[strRight] < 0 || mapDistance[strChoose] + nWeight < mapDistance[strRight])
{
mapDistance[strRight] = mapDistance[strChoose] + nWeight;
printf("update to:[%s] distance:[%d] \n", strRight.c_str(), mapDistance[strRight]);
}
}
}
}
return true;
}
};
int main(int argc, char* argv[])
{
CThroughMatrix throughMatrix;
// 加入顶点
throughMatrix.addVertex("A");
throughMatrix.addVertex("B");
throughMatrix.addVertex("C");
throughMatrix.addVertex("D");
throughMatrix.addVertex("E");
throughMatrix.addVertex("F");
throughMatrix.addVertex("G");
// 加入各有向边和距离
throughMatrix.addEdge("A", "B", 4, true);
throughMatrix.addEdge("A", "C", 6, true);
throughMatrix.addEdge("A", "D", 6, true);
throughMatrix.addEdge("B", "C", 1, true);
throughMatrix.addEdge("B", "E", 7, true);
throughMatrix.addEdge("C", "E", 6, true);
throughMatrix.addEdge("C", "F", 4, true);
throughMatrix.addEdge("D", "C", 2, true);
throughMatrix.addEdge("D", "F", 5, true);
throughMatrix.addEdge("E", "G", 6, true);
throughMatrix.addEdge("F", "E", 1, true);
throughMatrix.addEdge("F", "G", 8, true);
// 计算最短路径
std::vector<std::pair<std::string, int> > vecDistance;
throughMatrix.calcMinDistanceByDijkstra("A", vecDistance);
for (auto iter = vecDistance.begin(); iter != vecDistance.end(); ++iter)
{
printf("vertex:[%s] distance:[%d] \n", iter->first.c_str(), iter->second);
}
return 0;
}
代码基于最小生成树修改而来，增加了有向图和最短路径算法，但是删除了最小生成树的调用部分，如果读者朋友只需要借签算法部分的话，取本篇的代码就可以了。
编译：
g++ -o testdijkstra testdijkstra.cpp -std=c++11
运行结果：
add vertex:[A]
add vertex:[B]
add vertex:[C]
add vertex:[D]
add vertex:[E]
add vertex:[F]
add vertex:[G]
add edge:[A -> B] weight:[4]
add edge:[A -> C] weight:[6]
add edge:[A -> D] weight:[6]
add edge:[B -> C] weight:[1]
add edge:[B -> E] weight:[7]
add edge:[C -> E] weight:[6]
add edge:[C -> F] weight:[4]
add edge:[D -> C] weight:[2]
add edge:[D -> F] weight:[5]
add edge:[E -> G] weight:[6]
add edge:[F -> E] weight:[1]
add edge:[F -> G] weight:[8]
choose vertex:[A]
update to:[A] distance:[0]
update to:[B] distance:[4]
update to:[C] distance:[6]
update to:[D] distance:[6]
choose nearest vertex:[B] distance:[4]
update to:[C] distance:[5]
update to:[E] distance:[11]
choose nearest vertex:[C] distance:[5]
update to:[F] distance:[9]
choose nearest vertex:[D] distance:[6]
choose nearest vertex:[F] distance:[9]
update to:[E] distance:[10]
update to:[G] distance:[17]
choose nearest vertex:[E] distance:[10]
update to:[G] distance:[16]
choose nearest vertex:[G] distance:[16]
vertex:[G] no edge!
vertex:[A] distance:[0]
vertex:[B] distance:[4]
vertex:[C] distance:[5]
vertex:[D] distance:[6]
vertex:[F] distance:[9]
vertex:[E] distance:[10]
vertex:[G] distance:[16]
这是一个最短路径的探索过程，是求解全图中从某个顶点到其他所有顶点的距离问题，整个过程有近及远的发现和探知顶点，直到所有顶点完成探索。
但是狄克斯特拉算法只是求出了单个起点到其他顶点的距离，并不包括某两点间的最短路径，其实基于狄克斯特拉的探索过程是可以分析出两点之间的最短路径的，后面有机会再讲。
