前文講到了圖論中的最小生成樹問題誉察，個人覺得有必要繼續(xù)講講最短路徑算法的選路問題高诺。
什么是最短路徑？
互聯(lián)網(wǎng)技術(shù)和應(yīng)用的不斷發(fā)展峭梳，對當今網(wǎng)絡(luò)通信流量的要求不斷增大舰绘。流量大、速度快、費用低的傳輸方式是網(wǎng)絡(luò)傳輸?shù)年P(guān)鍵除盏。路徑最短叉橱、代價最低的網(wǎng)絡(luò)路由能夠大大降低通信成本、節(jié)約網(wǎng)絡(luò)資源者蠕，提高網(wǎng)絡(luò)資源的利用率窃祝。
最短路徑問題是組合優(yōu)化領(lǐng)域的經(jīng)典問題之一，它廣泛應(yīng)用于計算機科學踱侣、交通工程粪小、通信工程、系統(tǒng)工程抡句、運籌學探膊、信息論、控制理論等眾多領(lǐng)域待榔。Dijkstra算法是經(jīng)典的最短路徑算法逞壁。
狄克斯特拉算法
Dijkstra算法是經(jīng)典的最短路徑算法，其基本思想是：設(shè)置一個集合S存放已經(jīng)找到最短路徑的頂點锐锣，S的初始狀態(tài)只包含源點v腌闯，對vi∈V-S，假設(shè)從源點v到vi的有向邊為最短路徑雕憔。以后每求得一條最短路徑v, …, vk姿骏，就將vk加入集合S中，并將路徑v, …, vk , vi與原來的假設(shè)相比較斤彼，取路徑長度較小者為最短路徑分瘦，重復上述過程，直到集合V中全部頂點加入到集合S中琉苇。使用該算法找到的是全局最優(yōu)的最短路徑嘲玫，在網(wǎng)絡(luò)節(jié)點數(shù)量大、網(wǎng)絡(luò)邊數(shù)較多時翁潘，存在內(nèi)存占用大趁冈、時間復雜度高等不足歼争，并且Dijkstra算法不能很好地解決含必經(jīng)點約束的最短路徑問題拜马。
假設(shè)有這樣一張圖，需要求解從A點到其他點的最短路徑：
image.png
一個C++算法實現(xiàn)
拿上面的圖做為例子沐绒，具體實現(xiàn)下面的代碼：
#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;
}
}
}
// 找到權(quán)重最小的待探知頂點
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;
}
代碼基于最小生成樹修改而來扮超，增加了有向圖和最短路徑算法，但是刪除了最小生成樹的調(diào)用部分，如果讀者朋友只需要借簽算法部分的話出刷，取本篇的代碼就可以了璧疗。
編譯：
g++ -o testdijkstra testdijkstra.cpp -std=c++11
運行結(jié)果：
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]
這是一個最短路徑的探索過程，是求解全圖中從某個頂點到其他所有頂點的距離問題馁龟，整個過程有近及遠的發(fā)現(xiàn)和探知頂點崩侠，直到所有頂點完成探索。
但是狄克斯特拉算法只是求出了單個起點到其他頂點的距離坷檩，并不包括某兩點間的最短路徑却音，其實基于狄克斯特拉的探索過程是可以分析出兩點之間的最短路徑的，后面有機會再講矢炼。
