前言
最短路徑問題：從在帶權(quán)有向圖G中的某一頂點(diǎn)出發(fā)，找出一條通往另一頂點(diǎn)的最短路徑，最短也就是沿路徑各邊的權(quán)值總和達(dá)到最小。
單源最短路徑問題：給定一個(gè)圖G = ( V ， E ) G=(V，E)G=(V，E)，求源結(jié)點(diǎn)s ∈ V s∈Vs∈V到圖
中每個(gè)結(jié)點(diǎn)v ∈ V v∈Vv∈V的最短路徑
一、Dijkstra（迪克斯特拉）
1.方法：
針對(duì)一個(gè)帶權(quán)有向圖G，將所有結(jié)點(diǎn)分為兩組S和Q，S是已經(jīng)確定最短路徑的結(jié)點(diǎn)集合，在初始時(shí)
為空（初始時(shí)就可以將源節(jié)點(diǎn)s放入，畢竟源節(jié)點(diǎn)到自己的代價(jià)是0），Q 為其余未確定最短路徑
的結(jié)點(diǎn)集合，每次從Q 中找出一個(gè)起點(diǎn)到該結(jié)點(diǎn)代價(jià)最小的結(jié)點(diǎn)u ，將u 從Q 中移出，并放入S
中，對(duì)u 的每一個(gè)相鄰結(jié)點(diǎn)v 進(jìn)行松弛操作。松弛即對(duì)每一個(gè)相鄰結(jié)點(diǎn)v ，判斷源節(jié)點(diǎn)s到結(jié)點(diǎn)u
的代價(jià)與u 到v 的代價(jià)之和是否比原來s 到v 的代價(jià)更小，若代價(jià)比原來小則要將s 到v 的代價(jià)更新
為s 到u 與u 到v 的代價(jià)之和，否則維持原樣。如此一直循環(huán)直至集合Q 為空，即所有節(jié)點(diǎn)都已經(jīng)
查找過一遍并確定了最短路徑， Dijkstra算法每次都是選擇V-S中最小的路徑節(jié)點(diǎn)來進(jìn)行更新，并加入S中，所以該算法使用的是貪心策略。
核心就是從當(dāng)前選入的頂點(diǎn)當(dāng)中去找其直接相連的最小的邊，然后用這個(gè)最小邊相連的另一個(gè)頂點(diǎn)為起點(diǎn)，找與其直接相連邊中最小的邊（eg：與s直接相連的為t，y。最小的邊為5，即y頂點(diǎn)，其為s到y(tǒng)的最短距離，然后以y為起點(diǎn)，與y直接相連的有t，x，z。最小的邊為2即z點(diǎn)，y到z最短為2，所以s到z最短為7，以此類推，直到所有點(diǎn)都被當(dāng)過起點(diǎn)后結(jié)束）
2.代碼實(shí)現(xiàn)
void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
{
//dist存的src到其他點(diǎn)的最短路徑
// vector<int> pPath 記錄srci-其他頂點(diǎn)最短路徑父頂點(diǎn)數(shù)組
size_t srci = GetVertexIndex(src);
size_t n = _vertexs.size();
dist.resize(n, MAX_W);
pPath.resize(n, -1);
dist[srci] = 0;//自己到自己距離為0
pPath[srci] = srci;
// 已經(jīng)確定最短路徑的頂點(diǎn)集合
vector<bool> S(n, false);
for (size_t j = 0; j < n; ++j)
{
int u = srci;//u為當(dāng)前最短路徑頂點(diǎn)
W min = MAX_W;//min為起始點(diǎn)到u的距離
for (size_t i = 0; i < n; ++i)
{
if (S[i] == false && dist[i] < min)
{
u = i;
min = dist[i];
}
}
//找到與當(dāng)前起始點(diǎn)直接相連的最短路徑的頂點(diǎn)后
//將其位置置為true表明已經(jīng)選入
S[u] = true;
// 松弛算法：更新一遍u連接的所有邊，看是否能更新出更短連接路徑
for (size_t v = 0; v < n; ++v)
{
// 如果srci->u + u->k 比 srci->k更短 則進(jìn)行更新
if (S[v] == false && _matrix[u][v] != MAX_W
&& dist[u] + _matrix[u][v] < dist[v])
{
dist[v] = dist[u] + _matrix[u][v];
pPath[v] = u;
}
}
}
}
//打印路徑
void PrintShortPath(const V& src, const vector<W>& dist, const vector<int>& pPath) {
size_t srci = GetVertexIndex(src);
size_t n = _vertexs.size();
for (size_t i = 0; i < n; i++) {
if (i != srci) {
vector<int>path;
//path為src到其他頂點(diǎn)路徑
size_t parenti = i;
while (parenti != srci) {
path.push_back(parenti);
parenti = pPath[parenti];
}
path.push_back(srci);
//需要反轉(zhuǎn)一下，因?yàn)槲覀儚膕->x->v
//是從v的父親為x再推出x的父親為s才結(jié)束的
reverse(path.begin(), path.end());
for (auto index : path) {
cout << _vertexs[index] << "->";
}
cout << "權(quán)值和：" << dist[i] << endl;
}
}
}
Dijkstra算法存在的問題是不支持圖中帶負(fù)權(quán)路徑，如果帶有負(fù)權(quán)路徑，則可能會(huì)找不到一些路
徑的最短路徑。
二、FloydWarshall（弗洛伊德）
多源最短路徑：Floyd-Warshall算法是解決任意兩點(diǎn)間的最短路徑的一種算法。
1.方法
Floyd算法考慮的是一條最短路徑的中間節(jié)點(diǎn)，即簡(jiǎn)單路徑p={v1,v2,…,vn}上除v1和vn的任意節(jié)
點(diǎn)。
設(shè)k是p的一個(gè)中間節(jié)點(diǎn)，那么從i到j(luò)的最短路徑p就被分成i到k和k到j(luò)的兩段最短路徑p1，p2。p1
是從i到k且中間節(jié)點(diǎn)屬于{1，2，…，k-1}取得的一條最短路徑。p2是從k到j(luò)且中間節(jié)點(diǎn)屬于{1，
2，…，k-1}取得的一條最短路徑。
核心將中間經(jīng)過的k當(dāng)成所經(jīng)過s->…->j中間經(jīng)過的所有中間頂點(diǎn)集合中的一個(gè)，把中間的所有頂點(diǎn)看成k。
文章來源：http://www.zghlxwxcb.cn/news/detail-761911.html
2.代碼實(shí)現(xiàn)
void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvpPath)
{
size_t n = _vertexs.size();
vvDist.resize(n);
vvpPath.resize(n);
// 初始化權(quán)值和路徑矩陣
for (size_t i = 0; i < n; ++i)
{
vvDist[i].resize(n, MAX_W);
vvpPath[i].resize(n, -1);
}
//vvpPath[i][j]表示i->j,j的父親為i
// 直接相連的邊更新一下
//把目前已知直接相連的邊放入vvDist中，并更新vvpPath[i][j]
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
{
if (_matrix[i][j] != MAX_W)
{
vvDist[i][j] = _matrix[i][j];
vvpPath[i][j] = i;
}
if (i == j)
{
vvDist[i][j] = W();
}
}
}
// 最短路徑的更新i-> {其他頂點(diǎn)} ->j
//這里要進(jìn)行k次的原因是因?yàn)槲覀兯薪Y(jié)點(diǎn)都有可能
//成為src與dst的中間結(jié)點(diǎn)，所以要考慮所有情況
for (size_t k = 0; k < n; ++k)
{
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
{
// k 作為的中間點(diǎn)嘗試去更新i->j的路徑
if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W
&& vvDist[i][k] + vvDist[k][j] < vvDist[i][j])
{
vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
vvpPath[i][j] = vvpPath[k][j];
//因?yàn)檫@里k實(shí)際上是中間頂點(diǎn)集合
// 找跟j相連的上一個(gè)鄰接頂點(diǎn)
// 如果k->j 直接相連，上一個(gè)點(diǎn)就k，vvpPath[k][j]存就是k
// 如果k->j 沒有直接相連，k->...->x->j，vvpPath[k][j]存就是x
}
}
}
// 打印權(quán)值和路徑矩陣觀察數(shù)據(jù)
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
{
if (vvDist[i][j] == MAX_W)
{
//cout << "*" << " ";
printf("%3c", '*');
}
else
{
//cout << vvDist[i][j] << " ";
printf("%3d", vvDist[i][j]);
}
}
cout << endl;
}
cout << endl;
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
{
//cout << vvParentPath[i][j] << " ";
printf("%3d", vvpPath[i][j]);
}
cout << endl;
}
cout << "=================================" << endl;
}
}
};
完整源碼
如果對(duì)Graph這些代碼不太熟悉的小伙伴可以參考我之前寫的【數(shù)據(jù)結(jié)構(gòu)】圖的創(chuàng)建（鄰接矩陣，鄰接表）以及深度廣度遍歷（BFS,DFS）文章來源地址http://www.zghlxwxcb.cn/news/detail-761911.html
namespace matrix {
//V為頂點(diǎn)類型，W為邊權(quán)值類型，MAX_W為權(quán)值最大值也就是無效值
//Direction用來判斷是不是有向圖，false為無向圖
template<class V,class W,W MAX_W=INT_MAX,bool Direction=false>
class Graph {
public:
Graph() = default;
Graph(const V* a, size_t n) {
_vertexs.reserve(n);
for (size_t i = 0; i < n; i++) {
_vertexs.push_back(a[i]);
_indexMap[a[i]] = i;
//將頂點(diǎn)存入_vertexs，下標(biāo)映射存進(jìn)map
}
_matrix.resize(n);
for (size_t i = 0; i < _matrix.size(); i++) {
_matrix[i].resize(n, MAX_W);
//鄰接矩陣默認(rèn)初始值為無效值
}
}
size_t GetVertexIndex(const V& v) {
//獲得對(duì)應(yīng)頂點(diǎn)在數(shù)組中的下標(biāo)
auto it = _indexMap.find(v);
if (it != _indexMap.end()) {
return it->second;
//有這個(gè)頂點(diǎn)返回其下標(biāo)
}
else {
throw("頂點(diǎn)不存在");
return -1;
}
}
void _AddEdge(size_t srci, size_t dsti, const W& w) {
//存入權(quán)值
_matrix[srci][dsti] = w;
if (Direction == false) {
_matrix[dsti][srci] = w;
//無向圖要兩個(gè)方向都存
}
}
void AddEdge(const V& src, const V& dst, const W& w) {
//添加邊與頂點(diǎn)的關(guān)系。從src到dst方向的關(guān)系
size_t srci = GetVertexIndex(src);
size_t dsti = GetVertexIndex(dst);
//先獲取其對(duì)應(yīng)的下標(biāo)
_AddEdge(srci, dsti, w);
}
void Print() {
for (size_t i = 0; i < _vertexs.size(); i++) {
cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
}//打印頂點(diǎn)集
cout << endl;
//打印鄰接矩陣
for (size_t i = 0; i < _matrix.size(); i++) {
cout << i << " ";
for (size_t j = 0; j < _matrix[i].size(); j++) {
if (_matrix[i][j] == MAX_W) {
printf("%4c", '*');
}
else {
printf("%4d", _matrix[i][j]);
}
}
cout << endl;
}
}
void BFS(const V& src) {
size_t srci = GetVertexIndex(src);
queue<int>q;
q.push(srci);
vector<bool>visited(_vertexs.size(), false);
visited[srci] = true;//標(biāo)記這個(gè)頂點(diǎn)被訪問過了
int levelSize = 1;
while (!q.empty()) {
//levelSize為當(dāng)前層的大小
for (size_t i = 0; i < levelSize; i++) {
int front = q.front();
q.pop();
cout << front << ":" << _vertexs[front]<<" ";
for (size_t i = 0; i < _vertexs.size(); i++) {
if (_matrix[front][i] != MAX_W && visited[i] == false) {
q.push(i);
visited[i] = true;//標(biāo)記這個(gè)頂點(diǎn)被訪問過了
}
}
}
levelSize = q.size();//更新當(dāng)前層的數(shù)量
cout << endl;
}
cout << endl;
}
void _DFS(size_t srci, vector<bool>& visited) {
cout << srci << ":" << _vertexs[srci] << endl;
visited[srci] = true;//標(biāo)記這個(gè)頂點(diǎn)被訪問過了
for (size_t i = 0; i < _vertexs.size(); i++) {
if (_matrix[srci][i] != MAX_W && visited[i] == false) {
_DFS(i, visited);
}
}
}
void DFS(const V& src) {
size_t srci = GetVertexIndex(src);
vector<bool>visited(_vertexs.size(), false);
_DFS(srci, visited);
}
typedef Graph<V, W, MAX_W, false> Self;
//建立邊的類，保存邊的兩個(gè)頂點(diǎn)下標(biāo)和權(quán)值
struct Edge {
size_t _srci;
size_t _dsti;
W _w;
Edge(size_t srci,size_t dsti,W w)
:_srci(srci),
_dsti(dsti),
_w(w)
{}
bool operator>(const Edge& e)const {
return _w > e._w;//小根堆判斷
}
};
W Kruskal(Self& minTree)
{
//minTree為最小生成樹，剛開始什么都沒有
size_t n = _vertexs.size();
//初始化最小生成樹
minTree._vertexs = _vertexs;
minTree._indexMap = _indexMap;
minTree._matrix.resize(n);
for (size_t i = 0; i < n; ++i)
{
minTree._matrix[i].resize(n, MAX_W);
}
//我們每次選邊從全部邊中選出最小的（保證不構(gòu)成回路的情況）
//所以我們可以考慮用小根堆來存入邊，這樣每次方便找最小的
priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
{
if (i < j && _matrix[i][j] != MAX_W)
{
//將所有有效值邊放進(jìn)堆中
minque.push(Edge(i, j, _matrix[i][j]));
}
}
}
int size = 0;
W totalW = W();
UnionFindSet ufs(n);
// 選出n-1條邊
while (!minque.empty())
{
//取出最小邊
Edge min = minque.top();
minque.pop();
if (!ufs.InSet(min._srci, min._dsti))//判斷是否成環(huán)
{
//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] <<":"<<min._w << endl;
//不成環(huán)就將當(dāng)前邊放入最小生成樹當(dāng)中
minTree._AddEdge(min._srci, min._dsti, min._w);
//并把這兩個(gè)頂點(diǎn)放入同一個(gè)并查集集合當(dāng)中
ufs.Union(min._srci, min._dsti);
++size;
totalW += min._w;//權(quán)值總和增加
}
else
{
//cout << "構(gòu)成環(huán)：";
//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
}
}
if (size == n - 1)//邊數(shù)選夠說明最小生成樹
//創(chuàng)建成功
{
return totalW;
}
else
{
return W();
}
}
W Prim(Self& minTree, const W& src)
{
size_t srci = GetVertexIndex(src);
size_t n = _vertexs.size();
minTree._vertexs = _vertexs;
minTree._indexMap = _indexMap;
minTree._matrix.resize(n);
for (size_t i = 0; i < n; ++i)
{
minTree._matrix[i].resize(n, MAX_W);
}
vector<bool> X(n, false);
vector<bool> Y(n, true);
X[srci] = true;
Y[srci] = false;
// 從X->Y集合中連接的邊里面選出最小的邊
priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
// 先把srci連接的邊添加到小根堆中
for (size_t i = 0; i < n; ++i)
{
if (_matrix[srci][i] != MAX_W)
{
minq.push(Edge(srci, i, _matrix[srci][i]));
}
}
cout << "Prim開始選邊" << endl;
size_t size = 0;//選出邊的數(shù)量
W totalW = W();//權(quán)值之和
while (!minq.empty())
{
Edge min = minq.top();
minq.pop();
// 最小邊的目標(biāo)點(diǎn)也在X集合，則構(gòu)成環(huán)
if (X[min._dsti])
{
//cout << "構(gòu)成環(huán):";
//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
}
else
{
//從Y中選出頂點(diǎn)
minTree._AddEdge(min._srci, min._dsti, min._w);//加入最小生成樹
//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
X[min._dsti] = true;
Y[min._dsti] = false;
++size;
totalW += min._w;
if (size == n - 1)
break;
//把新加入頂點(diǎn)相關(guān)的邊都放入小根堆中
for (size_t i = 0; i < n; ++i)
{
if (_matrix[min._dsti][i] != MAX_W && Y[i])
{
minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
}
}
}
}
if (size == n - 1)
{
return totalW;
}
else
{
return W();
}
}
void PrintShortPath(const V& src, const vector<W>& dist, const vector<int>& pPath) {
size_t srci = GetVertexIndex(src);
size_t n = _vertexs.size();
for (size_t i = 0; i < n; i++) {
if (i != srci) {
vector<int>path;
//path為src到其他頂點(diǎn)路徑
size_t parenti = i;
while (parenti != srci) {
path.push_back(parenti);
parenti = pPath[parenti];
}
path.push_back(srci);
//需要反轉(zhuǎn)一下，因?yàn)槲覀儚膕->x->v
//是從v的父親為x再推出x的父親為s才結(jié)束的
reverse(path.begin(), path.end());
for (auto index : path) {
cout << _vertexs[index] << "->";
}
cout << "權(quán)值和：" << dist[i] << endl;
}
}
}
void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
{
//dist存的src到其他點(diǎn)的最短路徑
// vector<int> pPath 記錄srci-其他頂點(diǎn)最短路徑父頂點(diǎn)數(shù)組
size_t srci = GetVertexIndex(src);
size_t n = _vertexs.size();
dist.resize(n, MAX_W);
pPath.resize(n, -1);
dist[srci] = 0;//自己到自己距離為0
pPath[srci] = srci;
// 已經(jīng)確定最短路徑的頂點(diǎn)集合
vector<bool> S(n, false);
for (size_t j = 0; j < n; ++j)
{
int u = srci;//u為當(dāng)前最短路徑頂點(diǎn)
W min = MAX_W;//min為起始點(diǎn)到u的距離
for (size_t i = 0; i < n; ++i)
{
if (S[i] == false && dist[i] < min)
{
u = i;
min = dist[i];
}
}
//找到與當(dāng)前起始點(diǎn)直接相連的最短路徑的頂點(diǎn)后
//將其位置置為true表明已經(jīng)選入
S[u] = true;
// 松弛算法：更新一遍u連接的所有邊，看是否能更新出更短連接路徑
for (size_t v = 0; v < n; ++v)
{
// 如果srci->u + u->k 比 srci->k更短 則進(jìn)行更新
if (S[v] == false && _matrix[u][v] != MAX_W
&& dist[u] + _matrix[u][v] < dist[v])
{
dist[v] = dist[u] + _matrix[u][v];
pPath[v] = u;
}
}
}
}
void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvpPath)
{
size_t n = _vertexs.size();
vvDist.resize(n);
vvpPath.resize(n);
// 初始化權(quán)值和路徑矩陣
for (size_t i = 0; i < n; ++i)
{
vvDist[i].resize(n, MAX_W);
vvpPath[i].resize(n, -1);
}
//vvpPath[i][j]表示i->j,j的父親為i
// 直接相連的邊更新一下
//把目前已知直接相連的邊放入vvDist中，并更新vvpPath[i][j]
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
{
if (_matrix[i][j] != MAX_W)
{
vvDist[i][j] = _matrix[i][j];
vvpPath[i][j] = i;
}
if (i == j)
{
vvDist[i][j] = W();
}
}
}
// 最短路徑的更新i-> {其他頂點(diǎn)} ->j
//這里要進(jìn)行k次的原因是因?yàn)槲覀兯薪Y(jié)點(diǎn)都有可能
//成為src與dst的中間結(jié)點(diǎn)，所以要考慮所有情況
for (size_t k = 0; k < n; ++k)
{
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
{
// k 作為的中間點(diǎn)嘗試去更新i->j的路徑
if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W
&& vvDist[i][k] + vvDist[k][j] < vvDist[i][j])
{
vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
vvpPath[i][j] = vvpPath[k][j];
//因?yàn)檫@里k實(shí)際上是中間頂點(diǎn)集合
// 找跟j相連的上一個(gè)鄰接頂點(diǎn)
// 如果k->j 直接相連，上一個(gè)點(diǎn)就k，vvpPath[k][j]存就是k
// 如果k->j 沒有直接相連，k->...->x->j，vvpPath[k][j]存就是x
}
}
}
// 打印權(quán)值和路徑矩陣觀察數(shù)據(jù)
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
{
if (vvDist[i][j] == MAX_W)
{
//cout << "*" << " ";
printf("%3c", '*');
}
else
{
//cout << vvDist[i][j] << " ";
printf("%3d", vvDist[i][j]);
}
}
cout << endl;
}
cout << endl;
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
{
//cout << vvParentPath[i][j] << " ";
printf("%3d", vvpPath[i][j]);
}
cout << endl;
}
cout << "=================================" << endl;
}
}
private:
vector<V>_vertexs;//頂點(diǎn)集合
map<V, int>_indexMap;//存頂點(diǎn)與數(shù)組下標(biāo)的映射關(guān)系
vector<vector<W>>_matrix;//鄰接矩陣
};
}
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】最短路徑算法實(shí)現(xiàn)（Dijkstra（迪克斯特拉），F(xiàn)loydWarshall（弗洛伊德） ）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
