資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++ 演算法實現約翰遜演算法
這裡我們將看到約翰遜演算法，用於查詢兩個頂點之間的最短路徑。
此處的圖形如下。各邊之間的最短路徑如下所示。此程式將獲取頂點數、邊數以及具有其費用的邊。
輸入 − 頂點：3
邊：5
帶費用的邊 −
1 2 8
2 1 12
1 3 22
3 1 6
2 3 4
輸出 − 圖形距離矩陣。
| 0 | 8 | 12 |
| 10 | 0 | 4 |
| 6 | 14 | 0 |
演算法
johnsonAlgorithm(cost)
輸入 − 給定圖的成本矩陣。
輸出 − 任何頂點到任何頂點的最短路徑矩陣。
Begin Create another matrix ‘A’ same as cost matrix, if there is no edge between ith row and jth column, put infinity at A[i,j]. for k := 1 to n, do for i := 1 to n, do for j := 1 to n, do A[i, j] = minimum of A[i, j] and (A[i, k] + A[k, j]) done done done display the current A matrix End
示例
#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;
}
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++) { //take the input and store it into adj and cost matrix
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; //if there is no edge, put infinity
}
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]); //find minimum path from i to j through k
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";
}
}輸出
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
更新於： 30-Jul-2019
1K+ 瀏覽
廣告