• <table id="cjgd4"><strike id="cjgd4"></strike></table>
    <acronym id="cjgd4"><strong id="cjgd4"><address id="cjgd4"></address></strong></acronym><p id="cjgd4"><strong id="cjgd4"><small id="cjgd4"></small></strong></p>
    <acronym id="cjgd4"></acronym><table id="cjgd4"><strike id="cjgd4"></strike></table><td id="cjgd4"></td><acronym id="cjgd4"></acronym><acronym id="cjgd4"></acronym>

            溫馨提示×

            溫馨提示×

            您好,登錄后才能下訂單哦!

            密碼登錄×
            登錄注冊×
            其他方式登錄
            點擊 登錄注冊 即表示同意《億速云用戶服務條款》

            SPFA算法的實現原理及其應用介紹

            發布時間:2023-12-08 11:28:29 來源:億速云 閱讀:149 作者:栢白 欄目:開發技術

            本篇文章和大家了解一下SPFA算法的實現原理及其應用介紹。有一定的參考價值,有需要的朋友可以參考一下,希望對大家有所幫助。

            一、前言

            SPFA算法,全稱為Shortest Path Faster Algorithm,是求解單源最短路徑問題的一種常用算法,它可以處理有向圖或者無向圖,邊權可以是正數、負數,但是不能有負環。

            二、SPFA 算法

            1、SPFA算法的基本流程

            1. 初始化

            首先我們需要起點s到其他頂點的距離初始化為一個很大的值(比如9999999,像是 JAVA 中可以設置 Integer.MAX_VALUE 來使),并將起點s的距離初始化為0。同時,我們還需要將起點s入隊。

            SPFA算法的實現原理及其應用介紹

            2. 迭代

            每次從隊列中取出一個頂點u,遍歷所有從u出發的邊,對于邊(u,v)(其中v為從u可以到達的頂點),如果s->u->v的路徑長度小于s->v的路徑長度,那么我們就更新s->v的路徑長度,并將v入隊。

            SPFA算法的實現原理及其應用介紹

            3. 循環

            不斷進行步驟2,直到隊列為空。

            4. 判斷

            最后,我們可以得到從起點s到各個頂點的最短路徑長度,如果存在無窮小的距離,則說明從起點s無法到達該頂點。

            其次,需要注意的是,SPFA算法中存在負環問題。如果存在負環,則算法會陷入死循環。因此,我們需要添加一個計數器,記錄每個點進隊列的次數。當一個點進隊列的次數超過圖中節點個數時,就可以判定存在負環。

            2、代碼詳解

            以下是使用Java實現 SPFA算法的代碼,其中Graph類表示有向圖或無向圖,Vertex類表示圖中的一個頂點,Edge類表示圖中的一條邊。

            import java.util.*;
            class Graph {   // 圖
                private List<Vertex> vertices;  // 頂點集
                public Graph() {
                    vertices = new ArrayList<Vertex>();
                }
                public void addVertex(Vertex v) {   // 添加頂點
                    vertices.add(v);
                }   // 添加頂點
                public List<Vertex> getVertices() { // 返回頂點
                    return vertices;
                }   // 獲取頂點集
            }
            class Vertex {  // 點
                private int id; // 點 id
                private List<Edge> edges;   // 連接到該頂點的邊
                private int distance;   // 從源頂點到該頂點的最短距離,MAX_VALUE init
                private boolean visited;    // 在圖的遍歷過程中是否訪問過該頂點,false init
                public Vertex(int id) {
                    this.id = id;
                    edges = new ArrayList<Edge>();
                    distance = Integer.MAX_VALUE;
                    visited = false;
                }
                public int getId() {    // 獲取 id
                    return id;
                }
                public void addEdge(Edge e) {   // 將連接到該頂點邊添加到列表中
                    edges.add(e);
                }   // 添加圖到邊
                public List<Edge> getEdges() {  // 獲取連接到該頂點的邊集
                    return edges;
                }   // 獲取圖中邊
                public int getDistance() {  // 獲取從源頂點到該頂點的最短距離
                    return distance;
                }   // 獲取源頂點到該頂點的最短距離
                public void setDistance(int distance) { //設置最短距離
                    this.distance = distance;
                }   // 設置源頂點到該頂點的最短距離
                public boolean isVisited() {    // 獲取在圖的遍歷過程中是否訪問過該點
                    return visited;
                }   // 獲取圖遍歷過程中是否訪問過該點
                public void setVisited(boolean visited) {   // 設置在圖的遍歷過程中是否訪問過該點
                    this.visited = visited;
                }   // 設置圖遍歷過程中是否訪問過該點
            }
            class Edge {    // 邊
                private Vertex source;  // 源頂點
                private Vertex destination; // 目標頂點
                private int weight; // 邊的權重
                public Edge(Vertex source, Vertex destination, int weight) {
                    this.source = source;
                    this.destination = destination;
                    this.weight = weight;
                }
                public Vertex getSource() { // 返回源頂點
                    return source;
                }   // 獲取源點
                public Vertex getDestination() {    // 返回目標頂點
                    return destination;
                }   // 獲取目標頂點
                public int getWeight() {    // 獲取邊的權重
                    return weight;
                }   // 獲取邊的權重
            }
            // SPFA 算法
            public class SPFA { 
                public static void spfa(Graph graph, Vertex source) {
                    // 初始化
                    Queue<Vertex> queue = new LinkedList<Vertex>(); // 初始化一個頂點隊列,使用該隊列來跟中需要處理的頂點 
                    for (Vertex v : graph.getVertices()) {  // 初始化最短距離和是否訪問過該點
                        v.setDistance(Integer.MAX_VALUE);
                        v.setVisited(false);
                    }
                    source.setDistance(0); // 將源頂點到自身的最短距離設為0
                    queue.add(source);  // 將源頂點添加到隊列中
                    // 迭代
                    int count = 0;  // 用于檢測圖中的負環,count超過圖中頂點的總數,拋出異常
                    // 查找從一個源頂點到圖中所有其它頂點的最短路徑
                    while (!queue.isEmpty()) {  
                        Vertex u = queue.poll();    // 存儲SPFA算法正在處理的頂點,poll 方法將下一個頂點從隊列中取出
                        u.setVisited(false);    // 標記該頂點為未訪問,以便在算法中再次對其處理
                        // 查找部分,循環遍歷當前頂點 u 的所有邊
                        for (Edge e : u.getEdges()) {   
                            Vertex v = e.getDestination();  // 返回邊 e 的目標頂點給 v
                            int distance = u.getDistance() + e.getWeight(); // 計算源頂點到目標頂點的距離
                            if (distance < v.getDistance()) {
                                v.setDistance(distance);    // 更新最短距離
                                if (!v.isVisited()) {   // 如果該頂點未被訪問過
                                    queue.add(v);   // 將該頂點添加到隊列中
                                    v.setVisited(true); // 標記該頂點已被訪問
                                    count++;    // 負環 + 1
                                    if (count > graph.getVertices().size()) {   // 檢查 SPFA 算法處理的頂點數是否大于圖中頂點總數
                                        throw new RuntimeException("Negative cycle detected");
                                    }
                                }
                            }
                        }
                    }
                }
                public static void main(String[] args) {
                    // 構造圖
                    Graph graph = new Graph();
                    // 構造頂點
                    Vertex s = new Vertex(0);
                    Vertex a = new Vertex(1);
                    Vertex b = new Vertex(2);
                    Vertex c = new Vertex(3);
                    Vertex d = new Vertex(4);
                    // 點加邊
                    s.addEdge(new Edge(s, a, 2));
                    s.addEdge(new Edge(s, c, 1));
                    a.addEdge(new Edge(a, b, 3));
                    b.addEdge(new Edge(b, d, 2));
                    c.addEdge(new Edge(c, d, 1));
                    // 邊加點
                    graph.addVertex(s);
                    graph.addVertex(a);
                    graph.addVertex(b);
                    graph.addVertex(c);
                    graph.addVertex(d);
                    // 調用SPFA算法求解最短路徑
                    spfa(graph, s);
                    // 輸出結果
                    for (Vertex v :graph.getVertices()) {
                        System.out.println("Shortest distance from source to vertex " + v.getId() + " is " + v.getDistance()); 
                    } 
                } 
            }

            上面的代碼實現了SPFA算法,并計算了從給定源點到圖中其他所有頂點的最短路徑。主要思路如下:

            • 初始化:將所有頂點的距離設置為正無窮,將源點的距離設置為0,將源點加入隊列。

            • 迭代:從隊列中取出一個頂點u,遍歷它的所有鄰居v。如果u到源點的距離加上u到v的邊的權重小于v的距離,則更新v的距離,并將v加入隊列中。如果v已經在隊列中,則不需要再次添加。

            • 如果隊列為空,則算法結束。如果隊列非空,則回到步驟2。

            SPFA算法的時間復雜度取決于負權邊的數量。如果圖中沒有負權邊,算法的時間復雜度是O(E),其中E是邊的數量。但是如果圖中有負權邊,算法的時間復雜度將達到O(VE),其中V是頂點的數量,E是邊的數量。因此,為了避免算法的時間復雜度變得非常高,應盡可能避免在圖中使用負權邊。

            三、SPFA 算法已死

            這個問題引發了很多OI選手和出題人的討論,雖然 SPFA 算法在實際應用中具有一定的優勢,但它也有一些缺點,導致它被稱為"已死"的算法之一。以下是幾個原因:

            • 可能會進入負環:SPFA 算法可以處理負權邊,但是如果有負權環,算法將無法結束,因為每次都會沿著負權環一遍一遍地更新距離,導致算法陷入死循環。

            • 時間復雜度不穩定:在最壞情況下,SPFA 算法的時間復雜度可以達到 O ( V E ) O(VE) O(VE),其中 V V V 和 E E E 分別是圖中的頂點數和邊數。而在最好情況下,時間復雜度只有 O ( E ) O(E) O(E)。因此,SPFA 算法的時間復雜度是不穩定的。

            • 存在更好的算法:對于單源最短路徑問題,已經有更好的算法出現,如 Dijkstra 算法和 Bellman-Ford 算法。這些算法在時間復雜度和穩定性方面都比 SPFA 算法更優秀。

            雖然 SPFA 算法在某些情況下可以發揮出優勢,但是它的缺點也是無法忽視的,而且已經有更好的算法出現,不少大佬也或多或少的對 SPFA 算法進行了優化,更多優化的內容以及最短路徑算法可以在論文中找到。因此,SPFA 算法已經不是首選算法,也可以說是已經“死亡”了。

            SPFA算法的實現原理及其應用介紹

            以上就是SPFA算法的實現原理及其應用介紹的簡略介紹,當然詳細使用上面的不同還得要大家自己使用過才領會。如果想了解更多,歡迎關注億速云行業資訊頻道哦!

            向AI問一下細節

            免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

            AI

            国产片婬乱一级毛片视频|女同另类专区久久精品|色综合久久综合|欧美日韩在线旡码视频一区
          1. <table id="cjgd4"><strike id="cjgd4"></strike></table>
            <acronym id="cjgd4"><strong id="cjgd4"><address id="cjgd4"></address></strong></acronym><p id="cjgd4"><strong id="cjgd4"><small id="cjgd4"></small></strong></p>
            <acronym id="cjgd4"></acronym><table id="cjgd4"><strike id="cjgd4"></strike></table><td id="cjgd4"></td><acronym id="cjgd4"></acronym><acronym id="cjgd4"></acronym>