最短路径生成树(c++版 Dijkstra(即时和延时))

51 阅读 0 评论 34 点赞

我是靠谱客的博主无私冬日，最近开发中收集的这篇文章主要介绍最短路径生成树(c++版 Dijkstra(即时和延时))，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

EdgeWeightedDigraph.h

#pragma once
#include <memory>
#include <fstream>
#include <stdexcept>
template <typename T>
class Dijkstra;
template <typename T>
class LazyDijkstra;
template<typename T>
class EdgeWeightedDigraph
{
private:
class AdjacentcyList
{
public:
class DiEdge
{
public:
std::shared_ptr<DiEdge> next;
int v;
int w;
T weight;
public:
DiEdge(const int& s,const int& e,const T& t):v(s),w(e),weight(t),next(nullptr)
{
}
DiEdge() = default;
int from()
{
return v;
}
int to()
{
return w;
}
T Weight()
{
return weight;
}
};
std::shared_ptr<DiEdge> head;
class Iterator
{
private:
std::shared_ptr<DiEdge> it;
public:
Iterator(std::shared_ptr<DiEdge> i) :it(i)
{
}
bool operator == (const Iterator& rhs)const
{
return it == rhs.it;
}
bool operator != (const Iterator& rhs)const
{
return it != rhs.it;
}
Iterator operator ++()
{
it = it->next;
return *this;
}
DiEdge operator *()const
{
if (it == nullptr)
throw std::out_of_range("* nullptr error");
return *it;
}
};
Iterator begin()const
{
return Iterator(head);
}
Iterator end()const
{
return Iterator(nullptr);
}
AdjacentcyList():head(nullptr)
{
}
/*****************************************
函数名称:
addDiEdge
******************************************/
void addDiEdge(const int& s,const int& e,const T& t)
{
if (head == nullptr)
{
head = std::make_shared<DiEdge>(DiEdge(s, e, t));
return;
}
std::shared_ptr<DiEdge> curr = head;
while (curr->next != nullptr)
curr = curr->next;
curr->next = std::make_shared<DiEdge>(DiEdge(s, e, t));
return;
}
};
private:
std::unique_ptr<AdjacentcyList[]> adj;
int nV;
int nE;
public:
EdgeWeightedDigraph(const std::string& file):nE(0)
{
std::ifstream in(file);
in >> nV;
adj = std::move(std::unique_ptr<AdjacentcyList[]>(new AdjacentcyList[nV]));
while (!in.eof())
{
int pre, curr;
T weight;
in >> pre >> curr >> weight;
adj[pre].addDiEdge(pre, curr, weight);
++nE;
}
}
friend class Dijkstra<T>;
friend class LazyDijkstra<T>;
};

辅助数据结构类优先队列: priority_queue.h

#pragma once
#include <functional>
#include <memory>
template <typename T, typename Cmp = std::less<T>>
class priority_queue
{
private:
int SIZE = 100;
std::unique_ptr<T[]> heap;
int count;
public:
priority_queue():heap(new T[SIZE + 1]), count(0)
{
}
private:
void swim(int k)
{
while (k > 1 && Cmp()(heap[k], heap[k / 2]))
{
std::swap(heap[k], heap[k / 2]);
k = k / 2;
}
}
void sink(int k, const int& N)
{
while (2 * k <= N)
{
int j = 2 * k;
if (j < N && Cmp()(heap[j + 1], heap[j])) ++j;
if (Cmp()(heap[k], heap[j])) break;
std::swap(heap[k], heap[j]);
k = j;
}
}
void resize(const int& n)
{
std::unique_ptr<T[]> tmp(new T[n + 1]);
for (int i = 1; i <= count; ++i)
tmp[i] = heap[i];
heap = std::move(tmp);
SIZE = n;
}
public:
void push(const T& t)
{
if (count == SIZE)
resize(SIZE * 2);
heap[++count] = t;
swim(count);
}
T top()
{
if (count == 0)
throw std::out_of_range("error of top");
return heap[1];
}
void pop()
{
if (count == 0)
return;
if (count == 1)
{
--count;
return;
}
std::swap(heap[1], heap[count]);
--count;
sink(1, count);
if (count <= SIZE / 4)
resize(SIZE / 2);
}
bool empty()const
{
return count == 0;
}
/****************for pair*****************/
void push(const int& i, const T& t)
{
if (count == 0)
{
push(t);
return;
}
int pos = 1;
for (pos = 1; pos <= count; ++pos)
if (heap[pos].first == i)
break;
if (heap[pos].first == i)
{
if (count == 1)
{
heap[1] = t;
return;
}
heap[pos] = heap[count];
--count;
sink(pos, count);
push(t);
return;
}
else
push(t);
}
/*---------------------------------------*/
};

即时版 Dijkstra算法 Dijkstra.h

#pragma once
#include "priority_queue.h"
#include "EdgeWeightedDigraph.h"
template <typename T>
class Dijkstra
{
using Ed = typename EdgeWeightedDigraph<T>::AdjacentcyList::DiEdge;
private:
class Less
{
public:
Less() {}
bool operator ()(const std::pair<int, T>& lhs, const std::pair<int, T>& rhs)
{
return lhs.second < rhs.second;
}
};
private:
std::unique_ptr<T[]> disTo;
std::unique_ptr<Ed*[]> edge;
priority_queue<std::pair<int, T>,Less> pq;
int nv;
int s;
private:
void relax(EdgeWeightedDigraph<T> *ewg,const int& i)
{
for (auto &e : ewg->adj[i])
{
int w = e.to();
if (disTo[w] > disTo[i] + e.weight)
{
disTo[w] = disTo[i] + e.weight;
edge[w] = new Ed(i, w, e.weight);
pq.push(w, pair<int,T>(w,disTo[w]));
}
}
}
public:
Dijkstra(EdgeWeightedDigraph<T>* ewd,const int& s = 0):disTo(new T[ewd->nV]),edge(new Ed*[ewd->nV]),nv(ewd->nV),s(s)
{
for (int i = 0; i < ewd->nV; ++i)
{
disTo[i] = std::numeric_limits<T>::max();
edge[i] = nullptr;
}
disTo[s] = T{};
pq.push(s, pair<int, T>(s, 0.0));
while (!pq.empty())
{
relax(ewd, pq.top().first);
pq.pop();
}
}
T min_weight()
{
T ret{};
for (int i = 0; i < nv; ++i)
{
if (edge[i] == nullptr)
continue;
cout << edge[i]->from() << ends << edge[i]->to() << ends << edge[i]->weight << endl;
ret += edge[i]->weight;
}
return ret;
}
};

延时版Dijkstra算法 LazyDijkstra.h

#pragma once
#include "EdgeWeightedDigraph.h"
#include "priority_queue.h"
template <typename T>
class LazyDijkstra
{
using Ed = typename EdgeWeightedDigraph<T>::AdjacentcyList::DiEdge;
private:
class Less
{
public:
Less(){}
bool operator()(const std::pair<Ed,T>& lhs, const std::pair<Ed,T>& rhs)const
{
return lhs.second < rhs.second;
}
};
private:
std::unique_ptr<bool[]> marked;
std::unique_ptr<Ed*[]> edge;
std::unique_ptr<T[]> disTo;
priority_queue<std::pair<Ed,T>,Less> pq;
int nv;
int s; // 起点
private:
void relax(EdgeWeightedDigraph<T>* ewd,const int& i)
{
marked[i] = true;
for (auto &e : ewd->adj[i])
{
int w = e.to();
pq.push(std::pair<Ed,T>(e,disTo[w]));
}
}
public:
LazyDijkstra(EdgeWeightedDigraph<T> *ewd,const int& s = 0):marked(new bool[ewd->nV]),edge(new Ed*[ewd->nV]),disTo(new T[ewd->nV]),nv(ewd->nV),s(s)
{
for (int i = 0; i < ewd->nV; ++i)
{
edge[i] = nullptr;
disTo[i] = std::numeric_limits<T>::max();
}
disTo[s] = T{};
relax(ewd, s);
while (!pq.empty())
{
Ed e = pq.top().first;
int v = e.from();
int w = e.to();
pq.pop();
if (disTo[w] > disTo[v] + e.weight)
{
disTo[w] = disTo[v] + e.weight;
edge[w] = new Ed(v, w, e.weight);
relax(ewd, w);
}
}
}
T min_weight()
{
T ret{};
for (int i = 0; i < nv; ++i)
{
if (edge[i] == nullptr)
continue;
cout << edge[i]->from() << ends << edge[i]->to() << ends << edge[i]->weight << endl;
ret += edge[i]->weight;
}
return ret;
}
};

测试文件: test.txt

main.cpp

#include <iostream>
#include "EdgeWeightedDigraph.h"
#include "Dijkstra.h"
#include "LazyDijkstra.h"
using namespace std;
int main()
{
EdgeWeightedDigraph<double> ewd("test.txt");
Dijkstra<double> dj(&ewd,5);
cout << "即时版Dijkstra: " << dj.min_weight() << endl;
LazyDijkstra<double> ldj(&ewd,5);
cout << "延时版Dijkstra: " << ldj.min_weight();
system("pause");
return 0;
}