最短路径

最短路径是在加权有向图中，找到从一个顶点到达另一个顶点的成本最小的路径

1.加权有向图的数据结构

//加权有向边
class DirectedEdge
{
private:
    int vertax_from; //边的起点
    int vertax_to;   //边的终点
    double weight;   //边的权值
public:
    DirectedEdge(int v = 0, int w = 0, double weight = 0.0)
        : vertax_from(v), vertax_to(w), weight(weight) {}

    //返回边的起点
    int from() const { return vertax_from; }
    //返回边的终点
    int to() const { return vertax_to; }
    //返回边的权值
    double getWeight() const { return weight; }

    //字符串输出加权有向边
    string toString()
    {
        string s = "[ " + to_string(vertax_from) + "->" + to_string(vertax_to) + " , weight: " + to_string(weight) + " ]";
        return s;
    }

    //重载运算符
    friend bool operator<(const DirectedEdge &a, const DirectedEdge &b)
    {
        return a.getWeight() < b.getWeight();
    }

    friend bool operator>(const DirectedEdge &a, const DirectedEdge &b)
    {
        return a.getWeight() < b.getWeight();
    }

    friend bool operator==(const DirectedEdge &a, const DirectedEdge &b)
    {
        return a.getWeight() == b.getWeight() && a.from() == b.from() && a.to() == b.to();
    }

    friend bool operator!=(const DirectedEdge &a, const DirectedEdge &b)
    {
        return !(a.getWeight() == b.getWeight() && a.from() == b.from() && a.to() == b.to());
    }
};

代码实现：

/加权有向图
class EdgeWeightDigraph
{
private:
    int vertax;                         //顶点数
    int edge;                           //边数
    vector<list<DirectedEdge>> adjList; //邻接表
    vector<DirectedEdge> edges;         //所有有向边
public:
    //创建V个顶点的空图
    EdgeWeightDigraph(int V)
    {
        vertax = V;
        edge = 0;
        adjList.resize(vertax, list<DirectedEdge>());
    }

    //从文件读入加权有向图
    EdgeWeightDigraph(string in)
    {
        ifstream file(in);
        if (!file)
        {
            printf("can't open this file.\n");
            return;
        }

        string ch;
        int i = 0, e = 0;
        while (getline(file, ch))
        {
            istringstream iss(ch);
            if (i == 0)
            {
                iss >> vertax;
                edge = 0;
                adjList.resize(vertax, list<DirectedEdge>());
            }
            else if (i == 1)
                iss >> e;
            else if (i < e + 2)
            {
                int v, w;
                double weight;
                iss >> v >> w >> weight;
                addEdge(DirectedEdge(v, w, weight));
            }
            else
                break;
            i++;
        }
        file.close();
    }

    //添加一条加权有向边
    void addEdge(DirectedEdge e)
    {
        adjList[e.from()].push_back(e);
        edges.push_back(e);
        edge++;
    }

    //返回顶点数
    int V() { return vertax; }
    //返回边数
    int E() { return edge; }

    //返回v指出的边
    list<DirectedEdge> &adj(int v)
    {
        return adjList[v];
    }

    //返回所有的边
    vector<DirectedEdge> &getEdges()
    {
        return edges;
    }

    //字符串输出加权有向图
    string toString()
    {
        string s = to_string(vertax) + " vertices, " + to_string(edge) + " edges.\n";
        for (int v = 0; v < vertax; v++)
        {
            s += to_string(v) + ": ";
            for (auto e : adjList[v])
                s += e.toString();
            s += '\n';
        }
        return s;
    }
};

2.Floyd算法

Floyd算法是解决图中所有点到所有点的最短路径的一种方法，核心思想是在两个顶点之间插入一个或一个以上的中转点，比较经过与不经过中转点的距离哪个更短。

代码也十分简单，对于矩阵map[n][n]

for(int k = 0; i < n; k++)
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
	if(map[i][j] > map[i][k]+map[k][j])
		map[i][j] =  map[i][k]+map[k][j];

3.Dijkstra算法

Dijkstra算法是从未求出最短路径的顶点中，选出距离源点最近的一个顶点，将其的出边遍历一遍，更新其他未求出最短路径的点的距离，不断重复这一过程。

要实现Dijkstra算法，我们需要将distTo[s]初始化为0(源点)，其他元素初始化为正无穷。然后将源点的出边遍历，将更新的新顶点放入优先队列，然后再更新优先队列的顶点。直到所有可达顶点都更新过。

代码实现：

//Dijkstra算法
class Dijkstra
{
private:
    vector<DirectedEdge> edgeTo;    //到各点的最短路径
    vector<double> distTo;          //到各点的最短路径的权值
    map<int, double> pq;            //优先队列

    int getMin()    //优先队列的获取最小值操作
    {
        double minWeight = numeric_limits<double>::max();
        int minKey = 0;
        for (auto v : pq)
        {
            if (v.second < minWeight)
            {
                minWeight = v.second;
                minKey = v.first;
            }
        }
        return minKey;
    }

    void del(int v)      //优先队列的删除操作
    {
        auto it = pq.find(v);
        pq.erase(it);
    }

public:
    Dijkstra(EdgeWeightDigraph G, int s)
    {
        edgeTo.resize(G.V());
        distTo.resize(G.V(), numeric_limits<double>::max());
        distTo[s] = 0.0;
        pq[s] = distTo[s];
        while (!pq.empty())
        {
            int v = getMin();
            del(v);
            relax(G, v);
        }
    }

    //更新最短路径
    void relax(EdgeWeightDigraph G, int v)
    {
        for (auto e : G.adj(v))
        {
            int w = e.to();
            if (distTo[w] > distTo[v] + e.getWeight())
            {
                distTo[w] = distTo[v] + e.getWeight();
                edgeTo[w] = e;
                pq[w] = distTo[w];
            }
        }
    }

    //获取到v最短路径权值的接口
    double getDistTo(int v)
    {
        return distTo[v];
    }

    //获取v点可达路径的接口
    bool hasPathTo(int v)
    {
        return distTo[v] < numeric_limits<double>::max();
    }

    //获取到达v的路径
    vector<DirectedEdge> pathTo(int v)
    {
        vector<DirectedEdge> p;
        if (!hasPathTo(v))
            return p;
        stack<DirectedEdge> pathTemp;
        for (DirectedEdge e = edgeTo[v]; e != DirectedEdge(0, 0, 0.0); e = edgeTo[e.from()])
            pathTemp.push(e);
        while (!pathTemp.empty())
        {
            auto e = pathTemp.top();
            pathTemp.pop();
            p.push_back(e);
        }
        return p;
    }
};

4.拓扑排序

对于无环的加权有向图来说，有一种比Dijkstra算法更快、更简单的方法。只要将顶点按照拓扑排序的顺序更新最短路径的信息就可以获取源点到所有点的最短路径。

代码实现：

//拓扑排序
class Topologic
{
private:
    vector<int> indegree;   //入度数组
    vector<int> order;      //拓扑排序的顶点顺序

public:
    Topologic(EdgeWeightDigraph G)
    {
        //初始化入度数组
        indegree.resize(G.V(), 0);
        for (int v = 0; v < G.V(); v++)
            for (auto e : G.adj(v))
                indegree[e.to()]++;

        queue<int> q;

        //将入度为0的顶点放入队列
        for (int v = 0; v < G.V(); v++)
            if (indegree[v] == 0)
                q.push(v);
        int count = 0;

        //删除队列的结点,将它指向的结点入度-1
        //将入度减少到0的顶点放入队列
        while (!q.empty())
        {
            int v = q.front();
            q.pop();

            order.push_back(v);

            for (auto w : G.adj(v))
                if (!(--indegree[w.to()]))
                    q.push(w.to());
        }
    }

    //获取拓扑排序的接口
    vector<int> &getOrder()
    {
        return order;
    }
};

//无环加权有向图的最短路径
class AcyclicSP
{
private:
    vector<DirectedEdge> edgeTo; //到各点的最短路径
    vector<double> distTo;       //到各点的最短距离

public:
    AcyclicSP(EdgeWeightDigraph G, int s)
    {
        edgeTo.resize(G.V());
        distTo.resize(G.V(), numeric_limits<double>::max());
        distTo[s] = 0.0;

        Topologic topo(G);            //拓扑排序
        for (int v : topo.getOrder()) //按拓扑排序更新最短路径信息
            relax(G, v);
    }

    void relax(EdgeWeightDigraph G, int v) //更新结点最短路径信息
    {
        for (auto e : G.adj(v))
        {
            int w = e.to();
            if (distTo[w] > distTo[v] + e.getWeight())
            {
                distTo[w] = distTo[v] + e.getWeight();
                edgeTo[w] = e;
            }
        }
    }

    //获取到v最短路径权值的接口
    double getDistTo(int v)
    {
        return distTo[v];
    }

    //获取v点可达路径的接口
    bool hasPathTo(int v)
    {
        return distTo[v] < numeric_limits<double>::max();
    }

    //获取到达v的路径
    vector<DirectedEdge> pathTo(int v)
    {
        vector<DirectedEdge> p;
        if (!hasPathTo(v))
            return p;
        stack<DirectedEdge> pathTemp;
        for (DirectedEdge e = edgeTo[v]; e != DirectedEdge(0, 0, 0.0); e = edgeTo[e.from()])
            pathTemp.push(e);
        while (!pathTemp.empty())
        {
            auto e = pathTemp.top();
            pathTemp.pop();
            p.push_back(e);
        }
        return p;
    }
};

5.Bellman-Ford算法

Bellman-Ford算法可以解决除了含有负权重环的加权有向图。对于含有负权重环的图，讨论单点最短路径是没有意义的。

Bellman-Ford是将distTo[s]初始化为0，其他distTo元素初始化为无穷大，按任意顺序更新顶点最短路径，重复V遍。

代码实现：

//寻找加权有向环
class EdgeWeightCycleFinder
{
private:
    vector<bool> marked;    //标记
    vector<int> edgeTo;     
    vector<bool> onStack;   //s是否在栈中
    stack<int> cycle;       //环

public:
    EdgeWeightCycleFinder(EdgeWeightDigraph G)
    {
        marked.resize(G.V(), false);
        onStack.resize(G.V(), false);
        edgeTo.resize(G.V(), 0);
        for (int v = 0; v < G.V(); v++)
            if (!marked[v] && cycle.empty())
                dfs(G, v);
    }

    void dfs(EdgeWeightDigraph G, int v)
    {
        marked[v] = true;
        onStack[v] = true;
        for (auto e : G.adj(v))
        {
            int w = e.to();
            if (!cycle.empty())
                return;
            else if (!marked[w])
            {
                edgeTo[w] = v;
                dfs(G, w);
            }
            else if (onStack[w])
            {
                for (int x = v; x != w; x = edgeTo[x])
                    cycle.push(x);
                cycle.push(w);
                cycle.push(v);
            }
        }
        onStack[v] = false;
    }

    bool hasCycle()
    {
        return !cycle.empty();
    }

    vector<int> cyclePath()
    {
        vector<int> path;
        while (!cycle.empty())
        {
            path.push_back(cycle.top());
            cycle.pop();
        }
        return path;
    }
};

//Bellman-Ford算法
class BellmanFord
{
private:
    vector<double> distTo;          //最短路径的长度
    vector<DirectedEdge> edgeTo;    //各点的最短路径
    vector<bool> onQ;               //顶点是否在队列
    queue<int> q;                   
    int cost;                       //更新函数调用次数
    vector<int> cycle;              //负权重环

public:
    BellmanFord(EdgeWeightDigraph G, int s)
    {
        //初始化
        distTo.resize(G.V(), numeric_limits<double>::max());
        edgeTo.resize(G.V());
        onQ.resize(G.V(), false);
        cost = 0;

        //将源点放入队列
        distTo[s] = 0.0;
        q.push(s);
        onQ[s] = true;

        //按任意顺序更新
        while (!q.empty() && !hasNegativeCycle())
        {
            int v = q.front();
            q.pop();
            onQ[v] = false;
            relax(G, v);
        }
    }

    //更新最短路径信息
    void relax(EdgeWeightDigraph G, int v)
    {
        for (auto e : G.adj(v))
        {
            int w = e.to();
            if (distTo[w] > distTo[v] + e.getWeight())
            {
                distTo[w] = distTo[v] + e.getWeight();
                edgeTo[w] = e;
                if (!onQ[w])
                {
                    q.push(w);
                    onQ[w] = true;
                }
            }
            if (cost++ % G.V() == 0)
                findNegativeCycle();
        }
    }

     //获取到v最短路径权值的接口
    double getDistTo(int v)
    {
        return distTo[v];
    }

    //获取v点可达路径的接口
    bool hasPathTo(int v)
    {
        return distTo[v] < numeric_limits<double>::max();
    }

    //获取到达v的路径
    vector<DirectedEdge> pathTo(int v)
    {
        vector<DirectedEdge> p;
        if (!hasPathTo(v))
            return p;
        stack<DirectedEdge> pathTemp;
        for (DirectedEdge e = edgeTo[v]; e != DirectedEdge(0, 0, 0.0); e = edgeTo[e.from()])
            pathTemp.push(e);
        while (!pathTemp.empty())
        {
            auto e = pathTemp.top();
            pathTemp.pop();
            p.push_back(e);
        }
        return p;
    }

    //寻找负权重环
    void findNegativeCycle()
    {
        int V = edgeTo.size();
        EdgeWeightDigraph spt(V);
        for (int v = 0; v < V; v++)
            if (edgeTo[v] != DirectedEdge(0, 0, 0.0))
                spt.addEdge(edgeTo[v]);

        EdgeWeightCycleFinder cf(spt);

        cycle = cf.cyclePath();
    }

    //是否存在负权重环
    bool hasNegativeCycle()
    {
        return !cycle.empty();
    }

    //负权重环的路径
    vector<int> &negativeCycle()
    {
        return cycle;
    }
};

6.各个算法比较