각 정점 쌍 사이의 가중치와 함께 하나의 유향 그래프가 제공되며 두 개의 정점 u 및 v도 제공됩니다. 우리의 임무는 꼭짓점 u에서 꼭짓점 v까지의 최단 거리와 정확히 k개의 모서리 수를 찾는 것입니다.
이 문제를 해결하기 위해 정점 u에서 시작하여 모든 인접 정점으로 이동하고 k 값을 k - 1로 사용하여 인접 정점에 대해 반복합니다.
입력 및 출력
Input: The cost matrix of the graph. 0 10 3 2 ∞ 0 ∞ 7 ∞ ∞ 0 6 ∞ ∞ ∞ 0 Output: Weight of the shortest path is 9
알고리즘
shortKEdgePath(u, v, edge)
입력 - 정점 u와 v, 그리고 여러 모서리.
출력 - 최단 경로의 거리입니다.
Begin if edge = 0 and u = v, then return 0 if edge = 1 and cost[u, v] ≠ ∞, then return cost[u, v] if edge <= 0, then return ∞ set shortPath := ∞ for all vertices i, do if cost[u, i] ≠ ∞ and u ≠ i and v ≠ i, then tempRes := shortKEdgePath(i, v, edge - 1) if tempRes ≠ ∞, then shortPath = minimum of shortPath and (cost[u,i]+tempRes done return shortPath End
예시
#include <iostream> #define NODE 4 #define INF INT_MAX using namespace std; int cost[NODE][NODE] = { {0, 10, 3, 2}, {INF, 0, INF, 7}, {INF, INF, 0, 6}, {INF, INF, INF, 0} }; int minimum(int a, int b) { return (a<b)?a:b; } int shortKEdgePath(int u, int v, int edge) { if (edge == 0 && u == v) //when 0 edge, no path is present return 0; if (edge == 1 && cost[u][v] != INF) //when only one edge, and (u,v) is valid return cost[u][v]; if (edge <= 0) //when edge is -ve, there are infinity solution return INF; int shortPath = INF; for (int i = 0; i < NODE; i++) { //for all vertices i, adjacent to u if (cost[u][i] != INF && u != i && v != i) { int tempRes = shortKEdgePath(i, v, edge-1); if (tempRes != INF) shortPath = minimum(shortPath, cost[u][i] + tempRes); } } return shortPath; } int main() { int src = 0, dest = 3, k = 2; cout << "Weight of the shortest path is " << shortKEdgePath(src, dest, k); }
출력
Weight of the shortest path is 9