เส้นทางที่สั้นที่สุดของทุกคู่

อัลกอริธึมพาธที่สั้นที่สุดของคู่ทั้งหมดเรียกอีกอย่างว่าอัลกอริธึม Floyd-Warshall ใช้เพื่อค้นหาปัญหาเส้นทางที่สั้นที่สุดของคู่ทั้งหมดจากกราฟถ่วงน้ำหนักที่กำหนด ผลลัพธ์ของอัลกอริทึมนี้จะสร้างเมทริกซ์ซึ่งจะแสดงระยะทางต่ำสุดจากโหนดใดๆ ไปยังโหนดอื่นๆ ทั้งหมดในกราฟ

ในตอนแรกเมทริกซ์ผลลัพธ์จะเหมือนกับเมทริกซ์ต้นทุนที่กำหนดของกราฟ หลังจากนั้นเมทริกซ์เอาต์พุตจะได้รับการอัปเดตด้วยจุดยอด k ทั้งหมดเป็นจุดยอดระดับกลาง

ความซับซ้อนของเวลาของอัลกอริทึมนี้คือ O(V3) โดยที่ V คือจำนวนจุดยอดในกราฟ

อินพุต - เมทริกซ์ต้นทุนของกราฟ

0 3 6 ∞ ∞ ∞ ∞
3 0 2 1 ∞ ∞ ∞
6 2 0 1 4 2 ∞
∞ 1 1 0 2 ∞ 4
∞ ∞ 4 2 0 2 1
∞ ∞ 2 ∞ 2 0 1
∞ ∞ ∞ 4 1 1 0

เอาต์พุต - เมทริกซ์ของเส้นทางที่สั้นที่สุดของคู่ทั้งหมด

0 3 4 5 6 7 7
3 0 2 1 3 4 4
4 2 0 1 3 2 3
5 1 1 0 2 3 3
6 3 3 2 0 2 1
7 4 2 3 2 0 1
7 4 3 3 1 1 0

อัลกอริทึม

floydWarshal(ต้นทุน)

ป้อนข้อมูล − เมทริกซ์ต้นทุนของกราฟที่กำหนด

ผลผลิต − เมทริกซ์เป็นเส้นทางที่สั้นที่สุดระหว่างจุดยอดใดๆ ไปยังจุดยอดใดๆ

Begin
   for k := 0 to n, do
      for i := 0 to n, do
         for j := 0 to n, do
            if cost[i,k] + cost[k,j] < cost[i,j], then
               cost[i,j] := cost[i,k] + cost[k,j]
            done
         done
      done
      display the current cost matrix
End

ตัวอย่าง

#include<iostream>
#include<iomanip>
#define NODE 7
#define INF 999
using namespace std;
//Cost matrix of the graph
int costMat[NODE][NODE] = {
   {0, 3, 6, INF, INF, INF, INF},
   {3, 0, 2, 1, INF, INF, INF},
   {6, 2, 0, 1, 4, 2, INF},
   {INF, 1, 1, 0, 2, INF, 4},
   {INF, INF, 4, 2, 0, 2, 1},
   {INF, INF, 2, INF, 2, 0, 1},
   {INF, INF, INF, 4, 1, 1, 0}
};
void floydWarshal(){
   int cost[NODE][NODE]; //defind to store shortest distance from any node to any node
   for(int i = 0; i<NODE; i++)
      for(int j = 0; j<NODE; j++)
         cost[i][j] = costMat[i][j]; //copy costMatrix to new matrix
         for(int k = 0; k<NODE; k++){
            for(int i = 0; i<NODE; i++)
               for(int j = 0; j<NODE; j++)
                  if(cost[i][k]+cost[k][j] < cost[i][j])
                     cost[i][j] = cost[i][k]+cost[k][j];
   }
   cout << "The matrix:" << endl;
   for(int i = 0; i<NODE; i++){
      for(int j = 0; j<NODE; j++)
         cout << setw(3) << cost[i][j];
      cout << endl;
   }
}
int main(){
   floydWarshal();
}

ผลลัพธ์

The matrix:
0 3 5 4 6 7 7
3 0 2 1 3 4 4
5 2 0 1 3 2 3
4 1 1 0 2 3 3
6 3 3 2 0 2 1
7 4 2 3 2 0 1
7 4 3 3 1 1 0