从给定源到给定目的地的路径，在图中具有第 k 个最大权重
原文:https://www . geesforgeks . org/路径-从给定源到给定目的地-具有-kth-最大图中权重/
给定一个由 N 节点和 M 边组成的加权图，一个源顶点，目的地顶点，以及一个整数 K ，任务是找到图中从源到目的地权重最大的路径。
示例:
输入: N = 7，M = 8，源= 0，目的地= 6，K = 3，边[][] = {{0，1，10}，{1，2，10}，{2，3，10}，{0，3，40}，{3，4，2}，{4，5，3}，{5，6，3}，{4，6，8}，{2，5，5}} 输出:0 1 2 3 4【6 重量= 38。 路径:0 - > 1 - > 2 - > 3 - > 6。重量= 40。 路径:0 - > 3 - > 4 - > 5 - > 6。重量= 48。 路径:0 - > 3 - > 4 - > 6。重量= 50。 3rd最大加权路径是权重为 40 的路径。因此，具有权重 40 的路径是输出。
输入: N = 2，M = 1，源= 0，目的地= 1，K = 1，边[][] = {{0 1 25}}， T3】输出: 0 1
方法:给定的问题可以通过找到从给定源到目的地的所有路径并使用优先级队列找到第 K 个最大的权重来解决。按照以下步骤解决问题:
- 初始化邻接表，根据给定的边集边[][] 创建图形。
- 使用优先级队列初始化最大堆，比如说 PQ 作为大小为 K 的最小堆，以存储路径权重和路径作为从源到目的地的字符串。
- 初始化一个数组 访问了[] ，以标记一个顶点是否被访问。
- 遍历图到找到从源到目的地的所有路径。
- 创建一个实用类 Pair 作为 psf 和 wsf ，分别用于维护到目前为止获得的路径和权重。
- 在优先级队列中，执行以下操作:
- 完成上述步骤后，优先级队列顶端的元素给出包含 K 第T5【最大权重路径】的对。因此，打印该路径。
下面是上述方法的实现:
Java 语言(一种计算机语言，尤用于创建网站)
// Java program for the above approach
import java.io.*;
import java.util.*;
// Edge class represents a source,
// destination, weight of the edge
class Edge {
// Source
int src;
// Destination
int nbr;
// Weight
int wt;
// Constructor to create an Edge
Edge(int src, int nbr, int wt)
{
this.src = src;
this.nbr = nbr;
this.wt = wt;
}
}
// Pair class
class Pair implements Comparable<Pair> {
// Weight so far
int wsf;
// Path so far
String psf;
// Constructor to create a Pair
Pair(int wsf, String psf)
{
this.wsf = wsf;
this.psf = psf;
}
// Function to sort in increasing
// order of weights
public int compareTo(Pair o)
{
return this.wsf - o.wsf;
}
}
class GFG {
// Initializing the priority queue
static PriorityQueue<Pair> pq
= new PriorityQueue<>();
// Function to find the path from src to
// dest with Kth largest weight in the graph
public static void kthLargest(
ArrayList<Edge>[] graph,
int src, int dest,
boolean[] visited, int k,
String psf, int wsf)
{
// Base Case: When the
// destination has been reached
if (src == dest) {
// If pq has at most K elements
if (pq.size() < k) {
pq.add(new Pair(wsf, psf));
}
else if (wsf > pq.peek().wsf) {
pq.remove();
pq.add(new Pair(wsf, psf));
}
return;
}
// Mark the source node as visited
visited[src] = true;
// Iterating over all
// the neighbours of src
for (Edge e : graph[src]) {
// If neighbour is not visited
if (!visited[e.nbr]) {
kthLargest(graph, e.nbr,
dest, visited,
k, psf + e.nbr,
wsf + e.wt);
}
}
// Mark src as unvisited
visited[src] = false;
}
// Function to add edges
public static void addEdges(
ArrayList<Edge>[] graph)
{
// Adding a bidirectional edge
graph[0].add(new Edge(0, 1, 10));
graph[1].add(new Edge(1, 0, 10));
graph[1].add(new Edge(1, 2, 10));
graph[2].add(new Edge(2, 1, 10));
graph[2].add(new Edge(2, 3, 10));
graph[3].add(new Edge(3, 2, 10));
graph[0].add(new Edge(0, 3, 40));
graph[3].add(new Edge(3, 0, 40));
graph[3].add(new Edge(3, 4, 2));
graph[4].add(new Edge(4, 3, 2));
graph[4].add(new Edge(4, 5, 3));
graph[5].add(new Edge(5, 4, 3));
graph[5].add(new Edge(5, 6, 3));
graph[6].add(new Edge(6, 5, 3));
graph[4].add(new Edge(4, 6, 8));
graph[6].add(new Edge(6, 4, 8));
}
// Utility function to find the
// path with Kth largest weight
public static void kthLargestPathUtil(
int N, int M, int src,
int dest, int k)
{
@SuppressWarnings("unchecked")
// Arraylist to store edges
ArrayList<Edge>[] graph
= new ArrayList[2 * N];
for (int i = 0; i < 2 * N; i++) {
graph[i] = new ArrayList<>();
}
// Function to add edges
addEdges(graph);
// Stores if a vertex is visited or not
boolean[] visited = new boolean[N];
kthLargest(graph, src, dest,
visited, k, src + "",
0);
// Stores the kth largest weighted path
String path = pq.peek().psf;
// Traversing path string
for (int i = 0;
i < path.length(); i++) {
System.out.print(
path.charAt(i) + " ");
}
}
// Driver Code
public static void main(String[] args)
{
// No of vertices and Edges
int N = 7, M = 8;
// Source vertex
int src = 0;
// Destination vertex
int dest = 6;
int k = 3;
kthLargestPathUtil(N, M, src,
dest, k);
}
}
时间复杂度: O(V + E) 辅助空间: O(V)
版权属于：月萌API www.moonapi.com，转载请注明出处
