當我們使用BellmanFord算法時可以了解到，當我們第一次遍歷時松弛的邊是從源點可以直接到達的邊，接著再從這些頂點可以直接到達的邊進行松弛，以此類推。
所以基于以上思想我們可以去除BellmanFord算法中的無效循環。

首先我們可以選擇使用連個數組first和next，first用于記錄每條邊的第一條邊（最后一次輸入的邊），next用于記錄每條邊的上一條邊，如果沒有上一條邊則next為-1。再使用que數組（隊列）存放已經松弛過的頂點，book數組用來記錄頂點是否已經入隊。首先，我們需要先把源點入隊，且記錄下源點已經入隊。我們默認從源點到其他所有頂點的距離為999（無窮大）。我們從源點開始找出其第一條出邊（1->5 10）接下來的判斷就和BellmanFord中一樣，松弛該邊成功，頂點5入隊。接著找出源點開始的第二條邊（1->2 2），松弛成功，將2號頂點入隊。此時我們發現從源點開始可以直接到達的頂點都沒有了，然后我們把源點出隊，從隊列中的第二個頂點（5）開始向下搜索其可直接到達的邊進行松弛，以此類推，直到隊列中沒有頂點為止。

int[] u = new int[7]; int[] v = new int[7]; int[] w = new int[7];int[] first = new int[5];//頂點個數 int[] next = new int[7];//邊的條數int[] dis = new int[5];//原點到各個點之間的距離int[] book = new int[5];int head = 0; int tail = 1; int[] que = new int[20];private void initArrs() {for (int i = 1; i <= 4; i++) {dis[i] = 999;}for (int i = 0; i <= 4; i++) {first[i] = -1;}u[0] = 0;v[0] = 1;w[0] = 2;u[1] = 0;v[1] = 4;w[1] = 10;u[2] = 1;v[2] = 2;w[2] = 3;u[3] = 1;v[3] = 4;w[3] = 7;u[4] = 2;v[4] = 3;w[4] = 4;u[5] = 3;v[5] = 4;w[5] = 5;u[6] = 4;v[6] = 3;w[6] = 6;for (int i = 0; i <= 6; i++) {next[i] = first[u[i]];first[u[i]] = i;} }@Test public void testBellmanFordBetter() {initArrs();book[0] = 1;que[0] = 0;while (head < tail) {int k = first[que[head]];while (k != -1) {if (dis[v[k]] > dis[u[k]] + w[k]) {dis[v[k]] = dis[u[k]] + w[k];if (book[v[k]] == 0) {que[tail++] = v[k];book[v[k]] = 1;}}k = next[k];}book[que[head]] = 0;head++;}for (int i = 0; i <= 4; i++) {System.out.println(dis[i]);} }

轉載于:https://www.cnblogs.com/javathinker/p/7862202.html

總結

以上是生活随笔為你收集整理的BellmanFord的队列优化的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。