有向圖和最短路徑Dijkstra岂傲、Bellman-Ford、Floyd算法

本篇開始討論關(guān)于有向圖的算法子檀，無向圖是特殊的有向圖镊掖。
內(nèi)容概要：

  1. 有向圖的實(shí)現(xiàn)
  2. 最短路徑經(jīng)典算法實(shí)現(xiàn)

有向圖的實(shí)現(xiàn)

在無向圖的基礎(chǔ)上，修改得到有向圖的類褂痰。
有向無權(quán)圖類

/*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; // 頂點(diǎn)數(shù)
    private int E; // 邊數(shù)
    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){
        // 默認(rèn)構(gòu)建無向圖
        this(filename, false);
    }
    public boolean isDirected(){
        return directed;
    }
    public void validateVertex(int v){
        // 判斷頂點(diǎn)v是否合法
        if(v < 0 ||v >= V)
            throw new IllegalArgumentException("vertex " + v + "is invalid!");
    }
    public int V(){ // 返回頂點(diǎn)數(shù)
        return V;
    }
    public int E(){
        return E;
    }
    public boolean hasEdge(int v, int w){
        // 頂點(diǎn) v 到 w 是存在邊
        validateVertex(v);
        validateVertex(w);
        return adj[v].contains(w);
    }
    public Iterable<Integer> adj(int v){
        // 返回值可以是TreeSet，不過用 Iterable 接口更能體現(xiàn)面向?qū)ο?        // 返回和頂點(diǎn) v 相鄰的所有頂點(diǎn)
        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 ++){
            // 編程好習(xí)慣 i,j,k 作索引, v,w 作頂點(diǎn)
            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);
    }
}

有向帶權(quán)圖類

/*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;

// 無向和有向有權(quán)圖
public class WeightedGraph implements Cloneable {
    private int V; // 頂點(diǎn)數(shù)
    private int E; // 邊數(shù)
    private boolean directed;
    private TreeMap<Integer, Integer>[] adj; // 鄰接集合缩歪，存放鄰接點(diǎn)和對(duì)應(yīng)邊權(quán)值（可以是浮點(diǎn)型）

    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){
        // 默認(rèn)為無向圖
        this(filename, false);
    }
    public void validateVertex(int v){
        // 判斷頂點(diǎn)v是否合法
        if(v < 0 ||v >= V)
            throw new IllegalArgumentException("vertex " + v + "is invalid!");
    }
    public int V(){ // 返回頂點(diǎn)數(shù)
        return V;
    }
    public int E(){
        return E;
    }
    public boolean hasEdge(int v, int w){
        // 頂點(diǎn) v 到 w 是存在邊
        validateVertex(v);
        validateVertex(w);
        return adj[v].containsKey(w);
    }
    public Iterable<Integer> adj(int v){
        // 返回值可以是TreeSet，不過用 Iterable 接口更能體現(xiàn)面向?qū)ο?        // 返回和頂點(diǎn) v 相鄰的所有頂點(diǎn)
        validateVertex(v);
        return adj[v].keySet();
    }
    public int getWeight(int v, int w){
        // v-w 邊的權(quán)值
        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 ++){
            // 編程好習(xí)慣 i,j,k 作索引, v,w 作頂點(diǎn)
            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算法基于貪心策略和動(dòng)態(tài)規(guī)劃匪蝙。
設(shè)G=(V,E)是一個(gè)有向帶權(quán)圖苟翻，設(shè)置一個(gè)集合S記錄已求得最短路徑的頂點(diǎn)，具體過程如下：
（1）初始化把源點(diǎn)v放入S骗污，若v與V-S中頂點(diǎn)u有邊崇猫，則<u,v>有權(quán)值，若u不是v的出邊鄰接點(diǎn)需忿，則<u,v>距離置為無窮诅炉；
（2）從V-S中選取一個(gè)到中間頂點(diǎn)v距離最小的頂點(diǎn)k，把k加入S中屋厘；
（3）以k為新的中間頂點(diǎn)涕烧，修改源點(diǎn)到V-S中各頂點(diǎn)的距離；若從源點(diǎn)v經(jīng)過頂點(diǎn)k到頂點(diǎn)u的距離比不經(jīng)過頂點(diǎn)k短汗洒，則更新源點(diǎn)到頂點(diǎn)u的距離值為源點(diǎn)到頂點(diǎn)k的距離加上<k,u>邊上的權(quán)议纯。
（4）重復(fù)步驟（2）和（3）直到所有頂點(diǎn)都包含在S中。
該算法無法處理帶負(fù)權(quán)邊的圖溢谤，如下圖瞻凤，如果帶負(fù)權(quán)會(huì)有兩種情況一種是有負(fù)權(quán)環(huán)(環(huán)權(quán)值和為負(fù))憨攒，那么點(diǎn)對(duì)之間距離可以任意小阀参；另一種是距離無法更新到正確的結(jié)果上肝集。當(dāng)把一個(gè)節(jié)點(diǎn)選入集合S時(shí)，即意味著已經(jīng)找到了從源點(diǎn)到這個(gè)點(diǎn)的最短路徑蛛壳，但若存在負(fù)權(quán)邊杏瞻，就與這個(gè)前提矛盾，可能會(huì)出現(xiàn)得出的距離加上負(fù)權(quán)后比已經(jīng)得到S中的最短路徑還短衙荐。

帶負(fù)權(quán)

算法實(shí)現(xiàn)

import java.util.Arrays;

public class Dijkstra {
    private WeightedGraph G;
    private int s; // 源點(diǎn)s
    private int dis[]; // 源點(diǎn)到各點(diǎn)的最短距離
    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; // 初始狀態(tài)

        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){
        // 返回源點(diǎn) 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) + " ");
    }
}

時(shí)間復(fù)雜度
在上述實(shí)現(xiàn)中捞挥，每次確定到一個(gè)點(diǎn)的最短路徑，在確定到一個(gè)點(diǎn)的最短路徑時(shí)需要V次檢查以得到當(dāng)前未訪問的dis值最小的節(jié)點(diǎn)忧吟，故時(shí)間復(fù)雜度為O(V^2)
一個(gè)優(yōu)化
不過如果對(duì)于尋找當(dāng)前未訪問的dis值最小的節(jié)點(diǎn)使用優(yōu)先隊(duì)列(最小堆)树肃，這樣就可以做到在優(yōu)先隊(duì)列中動(dòng)態(tài)更新和取得dis[v]的最小值，可以將時(shí)間復(fù)雜度優(yōu)化到O(ElogE)瀑罗，實(shí)際應(yīng)用中大部分情況都是稀疏圖所以這是很好的一個(gè)優(yōu)化。

import java.util.*;

public class Dijkstra_pq {
    private WeightedGraph G;
    private int s; // 源點(diǎn)s
    private int dis[]; // 源點(diǎn)到各點(diǎn)的最短距離
    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; // 初始狀態(tài)
        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){
        // 返回源點(diǎn) 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));
    }
}

多源最短路
如果要求任意兩個(gè)頂點(diǎn)之間的最短路徑雏掠，只需要對(duì)每個(gè)頂點(diǎn)v調(diào)用一次Dijkstra算法斩祭。另外，如果只關(guān)注某兩個(gè)頂點(diǎn)之間的最短路徑乡话，可以將算法提前終止摧玫。

Bellman-Ford算法

Dijkstra算法雖然時(shí)間性能很優(yōu)秀，但它有一個(gè)很大的局限性就是無法處理帶負(fù)權(quán)邊的圖绑青。為此來看Bellman-Ford算法诬像，該算法使用動(dòng)態(tài)規(guī)劃。
算法過程
設(shè)G=(V,E)是一個(gè)有向帶權(quán)圖闸婴，Bellman-Ford算法具體過程如下：
（1）初始化dis[s]=0坏挠，其它dis值為無窮；
（2）然后對(duì)所有邊進(jìn)行一次松弛操作邪乍，這樣就求出了所有點(diǎn)降狠，經(jīng)過的邊數(shù)最多為1的最短路；
（3）再進(jìn)行1次松弛操作庇楞，則求出了所有點(diǎn)經(jīng)過的邊數(shù)最多為2的最短路榜配；
（4）一般共進(jìn)行松弛操作V-1次，重復(fù)到求出所有點(diǎn)經(jīng)過的邊數(shù)最多為V-1的最短路吕晌。
當(dāng)存在負(fù)權(quán)環(huán)時(shí)蛋褥，如果不停地兜圈子，那么這個(gè)最短路徑是可以無限小的睛驳，這時(shí)對(duì)于圖就沒有最短路徑烙心。另外對(duì)于可求最短路徑的圖膜廊，松弛操作可能比V-1小就可以了，V-1次可以保證求得最短路徑弃理。由此溃论，對(duì)于一般有向圖，如果再多進(jìn)行一次松弛操作后dis數(shù)組發(fā)生了更新痘昌，說明圖中含有負(fù)權(quán)環(huán)钥勋。
時(shí)間復(fù)雜度
由于是V-1輪松弛操作，每輪對(duì)每條邊進(jìn)行一次松弛辆苔，故時(shí)間復(fù)雜度為O(V*E)算灸。
算法實(shí)現(xiàn)

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;
                    }

        }
        // 再進(jìn)行一次松弛操作，如果dis發(fā)生更新說明存在負(fù)權(quán)環(huán)
        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(){
        // 是否有負(fù)權(quán)環(huán)
        return hasNegativeCycle;
    }

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

    public int disTo(int v){
        // 源點(diǎn)到 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));
    }
}

一個(gè)優(yōu)化
上述代碼在進(jìn)行松弛操作時(shí)對(duì)每個(gè)dis都進(jìn)行了檢查驻啤，實(shí)際上只有和當(dāng)前考慮頂點(diǎn)相鄰的頂點(diǎn)dis值才會(huì)被更新菲驴，為此可以使用一個(gè)隊(duì)列記錄已經(jīng)松弛過的節(jié)點(diǎn)，只關(guān)注每次松弛操作會(huì)影響的那些頂點(diǎn)的dis值骑冗。Bellman-Ford使用隊(duì)列優(yōu)化后的算法稱作SPFA算法赊瞬。

Floyd算法

Floyd算法解決的是任意兩點(diǎn)之間的最短路徑問題，基于動(dòng)態(tài)規(guī)劃贼涩。在一些問題中求得任意兩點(diǎn)對(duì)間的最短路徑是非常有用的巧涧，比如求圖的直徑。Floyd算法同樣可以處理含有帶負(fù)權(quán)邊的圖遥倦，并檢測負(fù)權(quán)環(huán)谤绳。
算法過程
設(shè)G=(V,E)是一個(gè)有向帶權(quán)圖，F(xiàn)loyd算法維護(hù)一個(gè)dis矩陣dis[v][w]表示頂點(diǎn)v到頂點(diǎn)w當(dāng)前最短路徑袒哥。具體過程如下：
（1）初始時(shí)dis[v][v]=0缩筛，如果v-w有邊，則dis[v][w]=邊上的權(quán)堡称，否則為無窮瞎抛；
（2）進(jìn)行循環(huán)：

    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];

關(guān)于算法正確性的說明：循環(huán)語義是從v到w經(jīng)過[0...t]這些點(diǎn)的最短路徑，當(dāng)t從0到V-1遍歷后却紧，一定可以求得最短路徑婿失。算法運(yùn)行結(jié)束后如果存在dis[v][v]<0，說明存在負(fù)權(quán)環(huán)啄寡。
算法實(shí)現(xiàn)

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();
            }
        }

    }
}

時(shí)間復(fù)雜度
Floyd算法的時(shí)間復(fù)雜度是O(V^3)豪硅，不過由于其代碼簡潔，且不包含其他復(fù)雜的數(shù)據(jù)結(jié)構(gòu)挺物，對(duì)于一般規(guī)模的數(shù)據(jù)還是可以的懒浮。

小結(jié)

Dijkstra算法解決單源最短路徑，時(shí)間復(fù)雜度O(ElogE)，使用有線隊(duì)列優(yōu)化后時(shí)間復(fù)雜度O(ElogV)砚著，不過Dijkstra算法不能處理含有負(fù)權(quán)邊的圖次伶。
Bellman-Ford算法也是解決單源最短路徑，時(shí)間復(fù)雜度是O(VE)稽穆，其基于隊(duì)列的優(yōu)化后是SPFA算法冠王，該算法最壞情況下時(shí)間復(fù)雜度也是O(VE)，它們都可以處理含有負(fù)權(quán)邊的圖舌镶。
Floyd算法的時(shí)間復(fù)雜度是O(V^3)柱彻，F(xiàn)loyd算法同樣可以處理含有負(fù)權(quán)邊的圖。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末餐胀，一起剝皮案震驚了整個(gè)濱河市哟楷，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌否灾，老刑警劉巖卖擅，帶你破解...
    沈念sama閱讀 211,290評(píng)論 6贊 491
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異墨技，居然都是意外死亡惩阶，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,107評(píng)論 2贊 385
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門扣汪，熙熙樓的掌柜王于貴愁眉苦臉地迎上來断楷，“玉大人，你說我怎么就攤上這事私痹。” “怎么了统刮？”我有些...
    開封第一講書人閱讀 156,872評(píng)論 0贊 347
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵紊遵，是天一觀的道長。 經(jīng)常有香客問我侥蒙，道長暗膜，這世上最難降的妖魔是什么？ 我笑而不...
    開封第一講書人閱讀 56,415評(píng)論 1贊 283
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任鞭衩，我火速辦了婚禮学搜，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘论衍。我一直安慰自己瑞佩，他們只是感情好，可當(dāng)我...
    茶點(diǎn)故事閱讀 65,453評(píng)論 6贊 385
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布坯台。 她就那樣靜靜地躺著炬丸，像睡著了一般。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上稠炬，一...
    開封第一講書人閱讀 49,784評(píng)論 1贊 290
  • 城市分裂傳說
    那天焕阿，我揣著相機(jī)與錄音，去河邊找鬼首启。 笑死暮屡，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的毅桃。 我是一名探鬼主播谆构，決...
    沈念sama閱讀 38,927評(píng)論 3贊 406
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼咕缎！你這毒婦竟也來了谴蔑？” 一聲冷哼從身側(cè)響起，我...
    開封第一講書人閱讀 37,691評(píng)論 0贊 266
  • 萬榮殺人案實(shí)錄
    序言：老撾萬榮一對(duì)情侶失蹤代承，失蹤者是張志新（化名）和其女友劉穎汁蝶，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體论悴，經(jīng)...
    沈念sama閱讀 44,137評(píng)論 1贊 303
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡掖棉，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,472評(píng)論 2贊 326
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了膀估。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片幔亥。...
    茶點(diǎn)故事閱讀 38,622評(píng)論 1贊 340
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖察纯，靈堂內(nèi)的尸體忽然破棺而出帕棉，到底是詐尸還是另有隱情，我是刑警寧澤饼记，帶...
    沈念sama閱讀 34,289評(píng)論 4贊 329
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布香伴，位于F島的核電站，受9級(jí)特大地震影響具则，放射性物質(zhì)發(fā)生泄漏即纲。R本人自食惡果不足惜，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,887評(píng)論 3贊 312
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一博肋、第九天 我趴在偏房一處隱蔽的房頂上張望低斋。 院中可真熱鬧，春花似錦匪凡、人聲如沸膊畴。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,741評(píng)論 0贊 21
  • 一樁弒父案病游，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽巴比。三九已至，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間轻绞，已是汗流浹背采记。 一陣腳步聲響...
    開封第一講書人閱讀 31,977評(píng)論 1贊 265
  • 情欲美人皮
    我被黑心中介騙來泰國打工， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留政勃，地道東北人唧龄。 一個(gè)月前我還...
    沈念sama閱讀 46,316評(píng)論 2贊 360
  • 代替公主和親
    正文 我出身青樓，卻偏偏與公主長得像奸远，于是被迫代替她去往敵國和親既棺。 傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,490評(píng)論 2贊 348

推薦閱讀更多精彩內(nèi)容

  • 前言 本專題旨在快速了解常見的數(shù)據(jù)結(jié)構(gòu)和算法懒叛。 在需要使用到相應(yīng)算法時(shí)丸冕，能夠幫助你回憶出常用的實(shí)現(xiàn)方案并且知曉其優(yōu)...
    蠻三刀醬閱讀 3,370評(píng)論 0贊 0
  • 圖的最短路徑 迪杰斯特拉算法 貝爾曼-福特算法 弗洛伊德算法 SPFA算法(中國西南交通大學(xué)段凡丁發(fā)明) 最短路徑...
    董澤平閱讀 457評(píng)論 0贊 1
  • 求圖的最短路徑（詳談Floyd和Dijkstra） （注：在這一部分起點(diǎn)、源點(diǎn)意思相近薛窥；點(diǎn)的距離胖烛、邊的長度、權(quán)值意...
    _黑色吊椅閱讀 2,764評(píng)論 0贊 9
  • 一诅迷、定義 在一幅加權(quán)有向圖中佩番，最短路徑是指從頂點(diǎn)s到頂點(diǎn)t的最短路徑是所有從s到t的路徑中的權(quán)重最小者。求解最短路...
    null12閱讀 2,453評(píng)論 0贊 4
  • 文 啟紅 碧水藍(lán)天夏風(fēng)柔 稻田沙洲飛白鷺 日落金光襯晚霞 柳樹倒...
    淡定人生風(fēng)雨路閱讀 5,277評(píng)論 139贊 217