数据结构
网络
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+ 浏览
广告