여기서 우리는 두 정점 사이의 최단 경로를 찾는 Johnson 알고리즘을 볼 것입니다.
그래프가 여기에 나와 있습니다. 모서리 사이의 최단 경로는 다음과 같습니다. 이 프로그램은 꼭짓점 수, 모서리 수 및 비용과 함께 모서리를 사용합니다.
입력 − 정점: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 |
알고리즘
johnson 알고리즘(비용)
입력 − 주어진 그래프의 비용 매트릭스.
출력 − 정점에서 정점 사이의 최단 경로에 대한 행렬입니다.
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