有向图和最短路径Dijkstra、Bellman-Ford、Fl

作者: Ice_spring | 来源:发表于2020-04-17 23:17 被阅读0次

本篇开始讨论关于有向图的算法，无向图是特殊的有向图。
内容概要：

有向图的实现
最短路径经典算法实现

有向图的实现

在无向图的基础上，修改得到有向图的类。
有向无权图类

/*Ice_spring 2020/4/15*/
import java.io.File;
import java.io.IOException;
import java.util.Scanner;
import java.util.TreeSet;

// 支持有向图和无向图
public class Graph implements Cloneable{
    private int V; // 顶点数
    private int E; // 边数
    private TreeSet<Integer>[] adj; // 邻接矩阵
    boolean directed;

    public Graph(String filename, boolean directed){
        this.directed = directed;
        File file = new File(filename);
        try(Scanner scanner = new Scanner(file)){

            V = scanner.nextInt();
            if(V < 0) throw new IllegalArgumentException("V must be a non-neg number!");
            adj = new TreeSet[V];

            for(int i = 0; i < V; i ++)
                adj[i] = new TreeSet<>();
            E = scanner.nextInt();
            if(E < 0) throw new IllegalArgumentException("E must be a non-neg number!");
            for(int i=0; i < E; i ++){
                int a = scanner.nextInt();
                validateVertex(a);
                int b = scanner.nextInt();
                validateVertex(b);
                // 本代码只处理简单图
                if(a == b) throw new IllegalArgumentException("检测到self-loop边！");
                if(adj[a].contains(b)) throw new IllegalArgumentException("Parallel Edges are detected!");
                adj[a].add(b);

                if(!directed)
                    adj[b].add(a);
            }
        }
        catch(IOException e){
            e.printStackTrace();//打印异常信息
        }
    }
    public Graph(String filename){
        // 默认构建无向图
        this(filename, false);
    }
    public boolean isDirected(){
        return directed;
    }
    public void validateVertex(int v){
        // 判断顶点v是否合法
        if(v < 0 ||v >= V)
            throw new IllegalArgumentException("vertex " + v + "is invalid!");
    }
    public int V(){ // 返回顶点数
        return V;
    }
    public int E(){
        return E;
    }
    public boolean hasEdge(int v, int w){
        // 顶点 v 到 w 是存在边
        validateVertex(v);
        validateVertex(w);
        return adj[v].contains(w);
    }
    public Iterable<Integer> adj(int v){
        // 返回值可以是TreeSet，不过用 Iterable 接口更能体现面向对象
        // 返回和顶点 v 相邻的所有顶点
        validateVertex(v);
        return adj[v];
    }

    public void removeEdge(int v, int w){
        // 删除 v-w 边
        validateVertex(v);
        validateVertex(w);
        if(adj[v].contains(w)) E --;
        adj[v].remove(w);
        if(!directed)
            adj[w].remove(v);
    }

    @Override
    public Object clone() {
        try {
            Graph cloned = (Graph) super.clone();
            cloned.adj = new TreeSet[V];
            for(int v = 0; v < V; v ++){
                cloned.adj[v] = new TreeSet<>();
                for(int w: this.adj[v])
                    cloned.adj[v].add(w);
            }
            return cloned;
        }catch (CloneNotSupportedException e){
            e.printStackTrace();
        }
        return null;
    }

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("V = %d, E = %d, directed = %b\n",V, E, directed));
        for(int v = 0; v < V; v ++){
            // 编程好习惯 i,j,k 作索引, v,w 作顶点
            sb.append(String.format("%d : ", v));

            for(int w: adj[v])
                sb.append(String.format("%d ", w));

            sb.append('\n');
        }
        return sb.toString();
    }

    public static void main(String args[]){
        Graph g = new Graph("g.txt", false);
        System.out.println(g);
    }
}

有向带权图类

/*Ice_spring 2020/4/16*/
import java.io.File;
import java.io.IOException;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

// 无向和有向有权图
public class WeightedGraph implements Cloneable {
    private int V; // 顶点数
    private int E; // 边数
    private boolean directed;
    private TreeMap<Integer, Integer>[] adj; // 邻接集合，存放邻接点和对应边权值（可以是浮点型）

    public WeightedGraph(String filename, boolean directed){
        this.directed = directed;
        File file = new File(filename);
        try(Scanner scanner = new Scanner(file)){

            V = scanner.nextInt();
            if(V < 0) throw new IllegalArgumentException("V must be a non-neg number!");
            adj = new TreeMap[V];

            for(int i = 0; i < V; i ++)
                adj[i] = new TreeMap<>();
            E = scanner.nextInt();
            if(E < 0) throw new IllegalArgumentException("E must be a non-neg number!");

            for(int i=0; i < E; i ++){
                int a = scanner.nextInt();
                validateVertex(a);
                int b = scanner.nextInt();
                validateVertex(b);
                int weight = scanner.nextInt();
                // 本代码只处理简单图
                if(a == b) throw new IllegalArgumentException("检测到self-loop边！");
                if(adj[a].containsKey(b)) throw new IllegalArgumentException("Parallel Edges are detected!");
                adj[a].put(b, weight);
                if(!directed)
                    adj[b].put(a, weight);
            }
        }
        catch(IOException e){
            e.printStackTrace();//打印异常信息
        }
    }
    public WeightedGraph(String filename){
        // 默认为无向图
        this(filename, false);
    }
    public void validateVertex(int v){
        // 判断顶点v是否合法
        if(v < 0 ||v >= V)
            throw new IllegalArgumentException("vertex " + v + "is invalid!");
    }
    public int V(){ // 返回顶点数
        return V;
    }
    public int E(){
        return E;
    }
    public boolean hasEdge(int v, int w){
        // 顶点 v 到 w 是存在边
        validateVertex(v);
        validateVertex(w);
        return adj[v].containsKey(w);
    }
    public Iterable<Integer> adj(int v){
        // 返回值可以是TreeSet，不过用 Iterable 接口更能体现面向对象
        // 返回和顶点 v 相邻的所有顶点
        validateVertex(v);
        return adj[v].keySet();
    }
    public int getWeight(int v, int w){
        // v-w 边的权值
        if(hasEdge(v, w))
            return adj[v].get(w);
        throw new IllegalArgumentException(String.format("No Edge %d-%d ", v, w));
    }

    public void removeEdge(int v, int w){
        // 删除 v-w 边
        validateVertex(v);
        validateVertex(w);
        if(adj[v].containsKey(w)) E --;
        adj[v].remove(w);
        if(!directed)
            adj[w].remove(v);
    }

    public boolean isDirected(){
        return directed;
    }
    @Override
    public Object clone() {
        try {
            WeightedGraph cloned = (WeightedGraph) super.clone();
            cloned.adj = new TreeMap[V];
            for(int v = 0; v < V; v ++){
                cloned.adj[v] = new TreeMap<>();
                for(Map.Entry<Integer, Integer> entry: adj[v].entrySet())// 遍历Map的方式
                    cloned.adj[v].put(entry.getKey(), entry.getValue());
            }
            return cloned;
        }catch (CloneNotSupportedException e){
            e.printStackTrace();
        }
        return null;
    }
    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("V = %d, E = %d, directed = %b\n",V, E, directed));
        for(int v = 0; v < V; v ++){
            // 编程好习惯 i,j,k 作索引, v,w 作顶点
            sb.append(String.format("%d : ", v));

            for(Map.Entry<Integer,Integer>entry: adj[v].entrySet())
                sb.append(String.format("(%d: %d)", entry.getKey(), entry.getValue()));

            sb.append('\n');
        }
        return sb.toString();
    }
    public static void main(String args[]){
        WeightedGraph g = new WeightedGraph("g.txt", true);
        System.out.println(g);
    }
}

Dijkstra算法

算法过程
Dijkstra算法基于贪心策略和动态规划。
设 $G=(V,E)$ 是一个有向带权图，设置一个集合 $S$ 记录已求得最短路径的顶点，具体过程如下：
（1）初始化把源点 $v$ 放入 $S$ ，若 $v$ 与 $V-S$ 中顶点 $u$ 有边，则 $<u,v>$ 有权值，若 $u$ 不是 $v$ 的出边邻接点，则 $<u,v>$ 距离置为无穷；
（2）从 $V-S$ 中选取一个到中间顶点 $v$ 距离最小的顶点k，把k加入S中；
（3）以 $k$ 为新的中间顶点，修改源点到 $V-S$ 中各顶点的距离；若从源点 $v$ 经过顶点 $k$ 到顶点 $u$ 的距离比不经过顶点 $k$ 短，则更新源点到顶点 $u$ 的距离值为源点到顶点 $k$ 的距离加上 $<k,u>$ 边上的权。
（4）重复步骤（2）和（3）直到所有顶点都包含在S中。
该算法无法处理带负权边的图，如下图，如果带负权会有两种情况一种是有负权环(环权值和为负)，那么点对之间距离可以任意小；另一种是距离无法更新到正确的结果上。

带负权

算法实现

import java.util.Arrays;

public class Dijkstra {
    private WeightedGraph G;
    private int s; // 源点s
    private int dis[]; // 源点到各点的最短距离
    private boolean visited[];

    public Dijkstra(WeightedGraph G, int s){
        this.G = G;
        G.validateVertex(s);
        this.s = s;
        dis = new int[G.V()];
        Arrays.fill(dis, 0x3f3f3f3f);
        dis[s] = 0; // 初始状态

        visited = new boolean[G.V()];
        while(true){
            int curdis = 0x3f3f3f3f, curv = -1;
            for(int v = 0; v < G.V(); v ++)
                if(!visited[v] && dis[v] < curdis){
                    curdis = dis[v];
                    curv = v;
                }
            if(curv == -1) break;

            visited[curv] = true;
            for(int w: G.adj(curv))
                if(!visited[w])
                    if(dis[curv] + G.getWeight(curv, w) < dis[w])
                        dis[w] = dis[curv] + G.getWeight(curv, w);
        }
    }

    public boolean isConnectedTo(int v){
        G.validateVertex(v);
        return visited[v];
    }

    public int distTo(int v){
        // 返回源点 s 到 v 的最短路径
        G.validateVertex(v);
        return dis[v];
    }
    public static void main(String args[]){
        WeightedGraph g = new WeightedGraph("g.txt");
        Dijkstra d = new Dijkstra(g, 0);
        for(int v = 0; v < g.V(); v ++)
            System.out.print(d.distTo(v) + " ");
    }
}

时间复杂度
在上述实现中，每次确定到一个点的最短路径，在确定到一个点的最短路径时需要V次检查以得到当前未访问的dis值最小的节点，故时间复杂度为 $O(V^2)$
一个优化
不过如果对于寻找当前未访问的dis值最小的节点使用优先队列(最小堆)，这样就可以做到在优先队列中动态更新和取得dis[v]的最小值，可以将时间复杂度优化到 $O(ElogE)$ ，实际应用中大部分情况都是稀疏图所以这是很好的一个优化。

import java.util.*;

public class Dijkstra_pq {
    private WeightedGraph G;
    private int s; // 源点s
    private int dis[]; // 源点到各点的最短距离
    private boolean visited[];
    private int pre[];
    private class Node implements Comparable<Node>{
        public int v, dis;
        public Node(int v, int dis){
            this.v = v;
            this.dis = dis;
        }
        @Override
        public int compareTo(Node another){
            return this.dis - another.dis;
        }
    }
    public Dijkstra_pq(WeightedGraph G, int s){
        this.G = G;
        G.validateVertex(s);
        this.s = s;
        dis = new int[G.V()];
        Arrays.fill(dis, 0x3f3f3f3f);
        pre = new int[G.V()];
        Arrays.fill(pre, -1);

        dis[s] = 0; // 初始状态
        pre[s] = s;

        visited = new boolean[G.V()];
        Queue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(s, 0));

        while(!pq.isEmpty()){

            int curv = pq.remove().v;
            if(visited[curv]) continue;
            visited[curv] = true;
            for(int w: G.adj(curv))
                if(!visited[w])
                    if(dis[curv] + G.getWeight(curv, w) < dis[w]) {
                        dis[w] = dis[curv] + G.getWeight(curv, w);
                        pre[w] = curv;
                        pq.add(new Node(w, dis[w]));

                    }
        }
    }

    public boolean isConnectedTo(int v){
        G.validateVertex(v);
        return visited[v];
    }

    public int distTo(int v){
        // 返回源点 s 到 v 的最短路径
        G.validateVertex(v);
        return dis[v];
    }

    public Iterable<Integer> path(int t){
        // 得到最短路径具体是什么
        ArrayList<Integer>res = new ArrayList<>();
        if(!isConnectedTo(t)) return res;
        int cur = t;
        while(cur !=s){
            res.add(cur);
            cur = pre[cur];
        }
        res.add(s);
        Collections.reverse(res);
        return res;
    }
    public static void main(String args[]){
        
        WeightedGraph g = new WeightedGraph("g.txt");
        Dijkstra_pq d = new Dijkstra_pq(g, 0);
        for(int v = 0; v < g.V(); v ++)
            System.out.print(d.distTo(v) + " ");
        System.out.println();
        System.out.println(d.path(3));
    }
}

多源最短路
如果要求任意两个顶点之间的最短路径，只需要对每个顶点v调用一次Dijkstra算法。另外，如果只关注某两个顶点之间的最短路径，可以将算法提前终止。

Bellman-Ford算法

Dijkstra算法虽然时间性能很优秀，但它有一个很大的局限性就是无法处理带负权边的图。为此来看Bellman-Ford算法，该算法使用动态规划。
算法过程
设 $G=(V,E)$ 是一个有向带权图，Bellman-Ford算法具体过程如下：
（1）初始化dis[s]=0，其它dis值为无穷；
（2）然后对所有边进行一次松弛操作，这样就求出了所有点，经过的边数最多为1的最短路；
（3）再进行1次松弛操作，则求出了所有点经过的边数最多为2的最短路；
（4）一般共进行松弛操作V-1次，重复到求出所有点经过的边数最多为V-1的最短路。
当存在负权环时，如果不停地兜圈子，那么这个最短路径是可以无限小的，这时对于图就没有最短路径。另外对于可求最短路径的图，松弛操作可能比V-1小就可以了，V-1次可以保证求得最短路径。由此，对于一般有向图，如果再多进行一次松弛操作后dis数组发生了更新，说明图中含有负权环。
时间复杂度
由于是V-1轮松弛操作，每轮对每条边进行一次松弛，故时间复杂度为 $O(V*E)$ 。
算法实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class BellmanFord {
    private WeightedGraph G;
    private int s;
    private int dis[];
    int pre[];
    private boolean hasNegativeCycle;

    public BellmanFord(WeightedGraph G, int s){
        this.G = G;
        G.validateVertex(s);
        this.s = s;
        dis = new int[G.V()];
        Arrays.fill(dis, 0x3f3f3f3f);
        dis[s] = 0;

        pre = new int[G.V()];
        Arrays.fill(pre, -1);
        pre[s] = s;

        for(int i = 1; i < G.V(); i ++){// V - 1 轮松弛操作

            for(int v = 0; v < G.V(); v ++)
                for(int w: G.adj(v))// 避免无穷加无穷溢出
                    if(dis[v] != 0x3f3f3f3f && dis[v] + G.getWeight(v, w) < dis[w]) {
                        dis[w] = dis[v] + G.getWeight(v, w);
                        pre[w] = v;
                    }

        }
        // 再进行一次松弛操作，如果dis发生更新说明存在负权环
        for(int v = 0; v < G.V(); v ++)
            for(int w: G.adj(v))// 避免无穷加无穷溢出
                if(dis[v] != 0x3f3f3f3f && dis[v] + G.getWeight(v, w) < dis[w])
                    hasNegativeCycle = true;
    }
    public boolean hasNegCycle(){
        // 是否有负权环
        return hasNegativeCycle;
    }

    public boolean isConnectedTo(int v){
        G.validateVertex(v);
        return dis[v] != 0x3f3f3f3f;
    }

    public int disTo(int v){
        // 源点到 v 的距离
        G.validateVertex(v);
        if(hasNegativeCycle)
            throw new RuntimeException("exist negative cycle!");
        return dis[v];
    }

    public Iterable<Integer>path(int t){
        ArrayList<Integer>res = new ArrayList<>();
        if(!isConnectedTo(t)) return res;
        int cur = t;
        while(cur !=s){
            res.add(cur);
            cur = pre[cur];
        }
        res.add(s);
        Collections.reverse(res);
        return res;
    }
    public static void main(String args[]){
        WeightedGraph g = new WeightedGraph("g.txt");
        BellmanFord bf = new BellmanFord(g, 0);
        if(!bf.hasNegCycle())
            for(int v = 0; v < g.V(); v ++)
                System.out.print(bf.disTo(v) + " ");
        System.out.println();
        System.out.println(bf.path(3));
    }
}

一个优化
上述代码在进行松弛操作时对每个dis都进行了检查，实际上只有和当前考虑顶点相邻的顶点dis值才会被更新，为此可以使用一个队列记录已经松弛过的节点，只关注每次松弛操作会影响的那些顶点的dis值。Bellman-Ford使用队列优化后的算法称作SPFA算法。

Floyd算法

Floyd算法解决的是任意两点之间的最短路径问题，基于动态规划。在一些问题中求得任意两点对间的最短路径是非常有用的，比如求图的直径。Floyd算法同样可以处理含有带负权边的图，并检测负权环。
算法过程
设 $G=(V,E)$ 是一个有向带权图，Floyd算法维护一个dis矩阵dis[v][w]表示顶点v到顶点w当前最短路径。具体过程如下：
（1）初始时dis[v][v]=0，如果v-w有边，则dis[v][w]=边上的权，否则为无穷；
（2）进行循环：

    for(int t = 0; t < V; t ++)
        for(int v = 0; v < V; v ++)
            for(int w = 0; w <V; w ++)
                if(dis[v][t] + dis[t][w] < dis[v][w])
                    dis[v][w] = dis[v][t] + dis[t][w];

关于算法正确性的说明：循环语义是从v到w经过[0...t]这些点的最短路径，当t从0到V-1遍历后，一定可以求得最短路径。算法运行结束后如果存在dis[v][v]<0，说明存在负权环。
算法实现

import java.util.Arrays;

public class Floyd {
    private WeightedGraph G;
    private int[][] dis;
    private boolean hasNegativeCycle = false;
    public Floyd(WeightedGraph G){
        this.G = G;
        dis = new int[G.V()][G.V()];
        for(int i = 0; i < G.V(); i ++)
            Arrays.fill(dis[i], 0x3f3f3f3f);
        for(int v = 0; v < G.V(); v ++){
            dis[v][v] = 0;
            for(int w: G.adj(v)){
                dis[v][w] = G.getWeight(v, w);
            }
        }

        for(int t = 0; t < G.V(); t ++)
            for(int v = 0; v < G.V(); v ++)
                for(int w = 0; w < G.V(); w ++)
                    if(dis[v][t] != 0x3f3f3f3f && dis[t][w] != 0x3f3f3f3f
                            && dis[v][t] + dis[t][w] < dis[v][w])
                        dis[v][w] = dis[v][t] + dis[t][w];

        for(int v = 0; v < G.V(); v ++)
            if(dis[v][v] < 0)
                hasNegativeCycle = true;

    }
    public boolean hasNegCycle(){
        return hasNegativeCycle;
    }
    public boolean isConnectedTo(int v, int w){
        G.validateVertex(v);
        G.validateVertex(w);
        return dis[v][w] != 0x3f3f3f3f;
    }
    public int disTo(int v, int w){
        if(isConnectedTo(v, w))
            return dis[v][w];
        throw new RuntimeException("v-w is not connected!");
    }
    public static void main(String args[]){
        WeightedGraph g = new WeightedGraph("g.txt");
        Floyd f = new Floyd(g);
        if(!f.hasNegativeCycle){
            for(int v = 0; v < g.V(); v ++) {
                for (int w = 0; w < g.V(); w++)
                    System.out.print(f.disTo(v, w) + " ");
                System.out.println();
            }
        }

    }
}

时间复杂度
Floyd算法的时间复杂度是 $O(V^3)$ ，不过由于其代码简洁，且不包含其他复杂的数据结构，对于一般规模的数据还是可以的。

小结

Dijkstra算法解决单源最短路径，时间复杂度 $O(ElogE)$ ，使用有线队列优化后时间复杂度 $O(ElogV)$ ，不过Dijkstra算法不能处理含有负权边的图。
Bellman-Ford算法也是解决单源最短路径，时间复杂度是 $O(VE)$ ，其基于队列的优化后是SPFA算法，该算法最坏情况下时间复杂度也是 $O(VE)$ ，它们都可以处理含有负权边的图。
Floyd算法的时间复杂度是 $O(V^3)$ ，Floyd算法同样可以处理含有负权边的图。

有向图和最短路径Dijkstra、Bellman-Ford、Fl

有向图的实现

Dijkstra算法

Bellman-Ford算法

Floyd算法

小结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

图论