Pathfind.cpp

#include "Metrograph.hpp"
#include "Pathfind.hpp"
#include "LinkedStack.hpp"

const double inf = 0x3f3f3f3f;
PathFind::PathFind(const MetroGraph* g){
    graph = g;
}
double PathFind::cal_w(int LineIn,const Edge& LineOut,const std::string& mode){
    double cost = 0;cost += LineOut.time;
        //如果上一站不是起点，且两站不在一条线上，那就需要换乘
        if (LineIn != -1 && LineIn != LineOut.line){
            if (mode == "最少换乘") cost += inf;//把换乘代价拉到极大,让dijkstra寻路时放弃需要换乘的方案
            else cost += 200.0;
        }
        if (mode == "舒适度优先"){
            cost += LineOut.crowd * 100;
        }
        return cost;
}
bool PathFind::dijkstra(int start,int end,std::string mode){
    int n = graph -> GetTotalStation();
    dis.assign(n+1,INF);vis.assign(n+1, false);PathNote.assign(n+1,{-1,-1});//预分配
    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> pq;//小根堆{代价,当前站,可以来当前站的站}
    dis[start] = 0;
    pq.push({0.0,start,-1});//代价为0，从起点出发，到达线路-1
    ld totaldistance = 0;ll cnt= 0;
    while (!pq.empty()){
        Node current = pq.top();
        pq.pop();
        int u = current.line_u;
        int line_in = current.line_in;
        if (vis[u]) continue;
        vis[u] = true;
        if (u == end) break;
        //下面找最近的邻节点
        const auto& adj = graph -> GetAdj();//获取图
        for (auto& edge : adj[u]){
            int v = edge.to;
            //异常处理
            if (edge.closed) continue;
            double w = cal_w(line_in,edge,mode);
            if (dis[u] + w < dis[v]){
                dis[v] = dis[u] + w;
                PathNote[v] = {u,edge.line};//v的前一站是u,通过edge.line乘坐而来
                pq.push({dis[v],v,edge.line});
            }
        }
        
    }
    return dis[end] != INF;
}

void PathFind::PrintPath(int start, int end) {
    if (dis[end] >= INF) {
        std::cout << "无法到达目的地！"<< "\n";
        return;
    }
    //链式栈回溯
    LinkedStack<int> stk;
    int current = end;
    while (current != -1){
        stk.push(current);
        current = PathNote[current].parent;
    }
    std::cout << "推荐路径: ";
    MetroGraph* g_ptr = const_cast<MetroGraph*>(graph);//强转指针
    while (!stk.empty()){
        int u = stk.top();stk.pop();
        std::cout << g_ptr->GetName(u);

        if (!stk.empty()){
            int nextnode = stk.top();
            int line = PathNote[nextnode].line;
            std::cout << " --(" << line << "号线)--> ";
        }
    }
    std::cout << "\n总代价: " << dis[end] << std::endl;
}

std::string PathFind::GetPathString(int start, int end) {
    if (dis[end] >= INF) return "无法到达";
    LinkedStack<int> stk;
    int curr = end;
    while (curr != -1) {
        stk.push(curr);
        curr = PathNote[curr].parent;
    }
    std::string res = "";
    MetroGraph* g_ptr = const_cast<MetroGraph*>(graph);
    while (!stk.empty()) {
        int u = stk.top(); stk.pop();
        res += g_ptr->GetName(u);
        if (!stk.empty()) res += "->";
    }
    return res;
}