C++基于拓扑排序的迭代法最短路径求解
#include <cstddef>
#include <iostream>
#include <sstream>
#include <string>
#include <array>
#include <memory>
#include <map>
#include <stack>
#include <vector>
using namespace std;
//控制台输入参数 顶点序列，和边权值
//a b c d e q 空格结束
//ab5 ae4 ac3 bc2 cd8 ce6 de10 q 空格结束
constexpr int MAX_COST = 9999;
union VexItem
{
char value_;
int index_;
};
class Vex
{
public:
Vex(Vex&&) = default;
Vex& operator =(Vex&&) = default;
Vex() = default;
explicit Vex(char ch, int cost = 0)
: cost_(cost)
, rudu_(0)
, next_(nullptr)
{
vex_item_.value_ = ch;
//cout << "init vex_item_.value_: " << vex_item_.value_ << endl;
}
explicit Vex(int index, int cost = 0)
: cost_(cost)
, rudu_(0)
, next_(nullptr)
{
vex_item_.index_ = index;
//cout << "init vex_item_.index_: " << vex_item_.index_ << endl;
}
VexItem vex_item_;
int cost_;
int rudu_;
shared_ptr<Vex> next_;
};
int main() {
constexpr int input_len{2 + 10};
constexpr auto vex_len{100};
int vex_count{0};
array<Vex, vex_len> vex;
map<char, int> vex_index;
auto string2num = [](const char* str)
{
int cost{0};
stringstream ss;
ss << str;
ss >> cost;
return cost;
};
cout << "input vex point" << endl;
for(int i = 0 ;; ++i)
{
array<char, input_len> input;
cin.getline(input.data(), input_len, ' ');
//cout << "you input vex point:" << input.data() << endl;
if(input[0] == 'q')
break;
vex[i] = Vex(input[0]);
vex_index[input[0]] = i;
vex_count++;
//cout << input[0] << " map to " << i << endl;
}
cin.ignore(std::numeric_limits< streamsize >::max(), '\n');
cout << "input vex pair and cost" << endl;
do
{
array<char, input_len> input;
cin.getline(input.data(), input_len, ' ');
//cout << "you input vex pair and cost:" << input.data() << endl;
if(input[0] == 'q')
break;
//cout << input[0] << "}}" << input[1] << endl;
auto from_index = vex_index[input[0]];
auto to_idnex = vex_index[input[1]];
auto tmp = make_shared<Vex>(to_idnex, string2num(input.data() + 2));
tmp->next_ = vex[from_index].next_;
vex[from_index].next_ = tmp;
vex[to_idnex].rudu_++;
}while(true);
//a b c d e q
//ab5 ae4 ac3 bc2 cd8 ce6 de10 q
stack<int> stack_vex;
vector<int> order_vex;
for(int i = 0; i < vex_count; i++)
{
auto& item = vex[i];
if(item.vex_item_.value_ == '\0' && item.vex_item_.index_ == 0)
break;
auto ptr = item.next_;
cout << "vex :" << item.vex_item_.value_ << ", rudu:" << item.rudu_ << endl;
if(ptr == nullptr)
{
cout << "end vex:" << item.vex_item_.value_ << endl;
}
for(; ptr != nullptr; ptr = ptr->next_)
{
cout << item.vex_item_.value_ << "-" << ptr->cost_ << "->"
<< vex[ptr->vex_item_.index_].vex_item_.value_ << " ";
}
cout << endl;
if(item.rudu_ == 0)
{
stack_vex.push(i);
}
}
while(!stack_vex.empty())
{
auto i = stack_vex.top();
stack_vex.pop();
order_vex.push_back(i);
auto ptr = vex[i].next_;
for(;ptr != nullptr; ptr = ptr->next_)
{
auto to_index = ptr->vex_item_.index_;
vex[to_index].rudu_--;
if(vex[to_index].rudu_ == 0)
{
stack_vex.push(to_index);
}
}
}
cout << "order_vex: " ;
for(auto& itme : order_vex)
{
cout << vex[itme].vex_item_.value_ << " " ;
}
cout << endl;
//求order_vex 第一个顶点到最后一个顶点的最短路径
int order_vex_len = order_vex.size();
const int start_vex = 1, end_vex = order_vex.back(); //指定路径前迄点
vector<int> cost(order_vex_len, MAX_COST);
vector<int> succ(order_vex_len, -1);
cost[end_vex] = 0;
int cur_vex_index = 0;
for(int i = 0; i < order_vex_len; ++i)
{
if(order_vex[i] == end_vex)
cur_vex_index = i;
}
while(order_vex[cur_vex_index] != start_vex)
{
int front_vex = order_vex[--cur_vex_index];
int front_vex_cost = MAX_COST;
int front_vex_succ = -1;
for(int i = 0; i < vex_count; ++i)
{
auto next = vex[front_vex].next_;
while(next != nullptr)
{
if(next->vex_item_.index_ == i && cost[i] + next->cost_ < front_vex_cost)
{
front_vex_cost = cost[i] + next->cost_;
front_vex_succ = i;
//cout << cur_vex_index << " " << front_vex_cost << " " << front_vex_succ << endl;
}
next = next->next_;
}
}
cost[front_vex] = front_vex_cost;
succ[front_vex] = front_vex_succ;
}
int path_index = start_vex;
cout << vex[start_vex].vex_item_.value_ << " to " << vex[end_vex].vex_item_.value_
<< " succ path is :" << endl << vex[start_vex].vex_item_.value_ << " ";
do
{
cout << vex[path_index = succ[path_index]].vex_item_.value_ << " ";
}while(path_index != end_vex);
return 1;
}
