<nav id="luije"><kbd id="luije"></kbd></nav>
<center id="luije"><form id="luije"></form></center><tt id="luije"><form id="luije"></form></tt>
<output id="luije"><xmp id="luije"></xmp></output>
  • <form id="luije"><acronym id="luije"></acronym></form>
  • <output id="luije"><font id="luije"><rp id="luije"></rp></font></output>
    <sub id="luije"><form id="luije"></form></sub>
  • <sub id="luije"></sub>
    <li id="luije"></li>
  • <acronym id="luije"><noframes id="luije"><sub id="luije"></sub></noframes></acronym>
  • <rp id="luije"><output id="luije"></output></rp>
    <rp id="luije"></rp>
  • <var id="luije"></var>
  • <acronym id="luije"><nav id="luije"></nav></acronym>
  • <li id="luije"><strike id="luije"><font id="luije"></font></strike></li>
    <form id="luije"></form>
  • <output id="luije"><table id="luije"><input id="luije"></input></table></output>
  • <var id="luije"><table id="luije"></table></var>
    溫馨提示×

    溫馨提示×

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

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

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

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

    本篇文章和大家了解一下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

    自拍偷自拍亚洲精品牛影院_99久热re在线精品99re8_国国产a国产片免费_成人午夜精品无码区
    <nav id="luije"><kbd id="luije"></kbd></nav>
    <center id="luije"><form id="luije"></form></center><tt id="luije"><form id="luije"></form></tt>
    <output id="luije"><xmp id="luije"></xmp></output>
  • <form id="luije"><acronym id="luije"></acronym></form>
  • <output id="luije"><font id="luije"><rp id="luije"></rp></font></output>
    <sub id="luije"><form id="luije"></form></sub>
  • <sub id="luije"></sub>
    <li id="luije"></li>
  • <acronym id="luije"><noframes id="luije"><sub id="luije"></sub></noframes></acronym>
  • <rp id="luije"><output id="luije"></output></rp>
    <rp id="luije"></rp>
  • <var id="luije"></var>
  • <acronym id="luije"><nav id="luije"></nav></acronym>
  • <li id="luije"><strike id="luije"><font id="luije"></font></strike></li>
    <form id="luije"></form>
  • <output id="luije"><table id="luije"><input id="luije"></input></table></output>
  • <var id="luije"><table id="luije"></table></var>