โปรแกรม C++ ใช้งาน Johnson's Algorithm

ที่นี่เราจะดู Johnson's Algorithm เพื่อหาเส้นทางสั้นที่สุดระหว่างสองโหนด (มีรูปภาพแสดงกราฟ)

กราฟที่ให้มา ระยะทางสั้นที่สุดระหว่างขอบ (edges) เป็นดังนี้ โปรแกรมจะรับจำนวนโหนด จำนวนขอบ และขอบพร้อมค่าใช้จ่าย

Input - Vertices: 3, Edges: 5
Edge with costs:
1 2 8
2 1 12
1 3 22
3 1 6
2 3 4

Output - Distance matrix of the graph:

อัลกอริทึม

johnsonAlgorithm(cost)

Input - Cost matrix of given Graph
Output - Matrix for shortest path between any vertex to any vertex

เริ่มต้น
  สร้างเมทริกซ์ 'A' เหมือน cost matrix ถ้าไม่มีขอบระหว่างแถว i และคอลัมน์ j ให้ใส่ infinity ที่ A[i,j]
  สำหรับ k := 1 ถึง n ทำ
    สำหรับ i := 1 ถึง n ทำ
      สำหรับ j := 1 ถึง n ทำ
        A[i, j] = minimum ของ A[i, j] และ (A[i, k] + A[k, j])
      จบลูป
    จบลูป
  จบลูป
  แสดงเมทริกซ์ A ปัจจุบัน
สิ้นสุด

ตัวอย่างโค้ด

#include <iostream>
#define INF 9999
using namespace std;

int min(int a, int b);
int cost[10][10], adj[10][10];

inline int min(int a, int b) {
    return (a < b) ? a : b;
}

int main() {
    int vert, edge, i, j, k, c;
    cout << "Enter no of vertices: ";
    cin >> vert;
    cout << "Enter no of edges: ";
    cin >> edge;
    cout << "Enter the EDGE Costs:\n";
    for (k = 1; k <= edge; k++) {
        cin >> i >> j >> c;
        adj[i][j] = cost[i][j] = c;
    }
    for (i = 1; i <= vert; i++)
        for (j = 1; j <= vert; j++) {
            if (adj[i][j] == 0 && i != j)
                adj[i][j] = INF;
        }
    for (k = 1; k <= vert; k++)
        for (i = 1; i <= vert; i++)
            for (j = 1; j <= vert; j++)
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
    cout << "Resultant adj matrix\n";
    for (i = 1; i <= vert; i++) {
        for (j = 1; j <= vert; j++) {
            if (adj[i][j] != INF)
                cout << adj[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

ผลลัพธ์

Enter no of vertices: 3
Enter no of edges: 5
Enter the EDGE Costs:
1 2 8
2 1 12
1 3 22
3 1 6
2 3 4
Resultant adj matrix
0 8 12
10 0 4
6 14 0