给定一个有向图，其中每条边的权重为1或2，求从给定源顶点“s”到给定目标顶点“t”的最短路径。预期时间复杂度为O（V+E）。 A. 简单解决方案 就是使用 Dijkstra最短路径算法 ，我们可以在O（E+VLogV）时间内得到一条最短路径。
null
如何在O（V+E）时间内完成？ 这个想法是使用 BFS 关于BFS的一个重要观察是，BFS中使用的路径在任意两个顶点之间的边数总是最少的。因此，如果所有边的权重相同，我们可以使用BFS来寻找最短路径。对于这个问题，我们可以修改图并将所有权重为2的边拆分为两条权重为1的边。在修改后的图中，我们可以使用BFS来寻找最短路径。
需要多少个新的中间顶点？ 我们需要为每个源顶点添加一个新的中间顶点。原因很简单，如果我们在u和v之间添加一个中间顶点x，如果我们在y和z之间添加相同的顶点，那么新的路径u到z，y到v被添加到图中，这可能在原始图中已经存在。因此，在有V个顶点的图中，我们需要V个额外的顶点。
下面是C++实现上述思想。在下面的实现中，在图中创建2*V顶点，对于每条边（u，V），我们将其拆分为两条边（u，u+V）和（u+V，w）。这样我们可以确保为每个源顶点添加不同的中间顶点。
C/C++
// Program to shortest path from a given source vertex ‘s’ to // a given destination vertex ‘t’. Expected time complexity // is O(V+E). #include<bits/stdc++.h> using namespace std; // This class represents a directed graph using adjacency // list representation class Graph { int V; // No. of vertices list< int > *adj; // adjacency lists public : Graph( int V); // Constructor void addEdge( int v, int w, int weight); // adds an edge // finds shortest path from source vertex ‘s’ to // destination vertex ‘d’. int findShortestPath( int s, int d); // print shortest path from a source vertex ‘s’ to // destination vertex ‘d’. int printShortestPath( int parent[], int s, int d); }; Graph::Graph( int V) { this ->V = V; adj = new list< int >[2*V]; } void Graph::addEdge( int v, int w, int weight) { // split all edges of weight 2 into two // edges of weight 1 each. The intermediate // vertex number is maximum vertex number + 1, // that is V. if (weight==2) { adj[v].push_back(v+V); adj[v+V].push_back(w); } else // Weight is 1 adj[v].push_back(w); // Add w to v’s list. } // To print the shortest path stored in parent[] int Graph::printShortestPath( int parent[], int s, int d) { static int level = 0; // If we reached root of shortest path tree if (parent[s] == -1) { cout << "Shortest Path between " << s << " and " << d << " is " << s << " " ; return level; } printShortestPath(parent, parent[s], d); level++; if (s < V) cout << s << " " ; return level; } // This function mainly does BFS and prints the // shortest path from src to dest. It is assumed // that weight of every edge is 1 int Graph::findShortestPath( int src, int dest) { // Mark all the vertices as not visited bool *visited = new bool [2*V]; int *parent = new int [2*V]; // Initialize parent[] and visited[] for ( int i = 0; i < 2*V; i++) { visited[i] = false ; parent[i] = -1; } // Create a queue for BFS list< int > queue; // Mark the current node as visited and enqueue it visited[src] = true ; queue.push_back(src); // 'i' will be used to get all adjacent vertices of a vertex list< int >::iterator i; while (!queue.empty()) { // Dequeue a vertex from queue and print it int s = queue.front(); if (s == dest) return printShortestPath(parent, s, dest); queue.pop_front(); // Get all adjacent vertices of the dequeued vertex s // If a adjacent has not been visited, then mark it // visited and enqueue it for (i = adj[s].begin(); i != adj[s].end(); ++i) { if (!visited[*i]) { visited[*i] = true ; queue.push_back(*i); parent[*i] = s; } } } } // Driver program to test methods of graph class int main() { // Create a graph given in the above diagram int V = 4; Graph g(V); g.addEdge(0, 1, 2); g.addEdge(0, 2, 2); g.addEdge(1, 2, 1); g.addEdge(1, 3, 1); g.addEdge(2, 0, 1); g.addEdge(2, 3, 2); g.addEdge(3, 3, 2); int src = 0, dest = 3; cout << "Shortest Distance between " << src << " and " << dest << " is " << g.findShortestPath(src, dest); return 0; } |
JAVA
// Java to shortest path from a given source vertex 's' to // a given destination vertex 't'. Expected time complexity // is O(V+E). import java.util.*; class GFG { // This class represents a directed graph using adjacency // list representation static class Graph { int V; // No. of vertices Vector<Integer>[] adj; // No. of vertices static int level; // Constructor @SuppressWarnings ( "unchecked" ) Graph( int V) { this .V = V; this .adj = new Vector[ 2 * V]; for ( int i = 0 ; i < 2 * V; i++) this .adj[i] = new Vector<>(); } // adds an edge public void addEdge( int v, int w, int weight) { // split all edges of weight 2 into two // edges of weight 1 each. The intermediate // vertex number is maximum vertex number + 1, // that is V. if (weight == 2 ) { adj[v].add(v + this .V); adj[v + this .V].add(w); } else // Weight is 1 adj[v].add(w); // Add w to v's list. } // print shortest path from a source vertex 's' to // destination vertex 'd'. public int printShortestPath( int [] parent, int s, int d) { level = 0 ; // If we reached root of shortest path tree if (parent[s] == - 1 ) { System.out.printf( "Shortest Path between" + "%d and %d is %s " , s, d, s); return level; } printShortestPath(parent, parent[s], d); level++; if (s < this .V) System.out.printf( "%d " , s); return level; } // finds shortest path from source vertex 's' to // destination vertex 'd'. // This function mainly does BFS and prints the // shortest path from src to dest. It is assumed // that weight of every edge is 1 public int findShortestPath( int src, int dest) { boolean [] visited = new boolean [ 2 * this .V]; int [] parent = new int [ 2 * this .V]; // Initialize parent[] and visited[] for ( int i = 0 ; i < 2 * this .V; i++) { visited[i] = false ; parent[i] = - 1 ; } // Create a queue for BFS Queue<Integer> queue = new LinkedList<>(); // Mark the current node as visited and enqueue it visited[src] = true ; queue.add(src); while (!queue.isEmpty()) { // Dequeue a vertex from queue and print it int s = queue.peek(); if (s == dest) return printShortestPath(parent, s, dest); queue.poll(); // Get all adjacent vertices of the dequeued vertex s // If a adjacent has not been visited, then mark it // visited and enqueue it for ( int i : this .adj[s]) { if (!visited[i]) { visited[i] = true ; queue.add(i); parent[i] = s; } } } return 0 ; } } // Driver Code public static void main(String[] args) { // Create a graph given in the above diagram int V = 4 ; Graph g = new Graph(V); g.addEdge( 0 , 1 , 2 ); g.addEdge( 0 , 2 , 2 ); g.addEdge( 1 , 2 , 1 ); g.addEdge( 1 , 3 , 1 ); g.addEdge( 2 , 0 , 1 ); g.addEdge( 2 , 3 , 2 ); g.addEdge( 3 , 3 , 2 ); int src = 0 , dest = 3 ; System.out.printf( "Shortest Distance between" + " %d and %d is %d" , src, dest, g.findShortestPath(src, dest)); } } // This code is contributed by // sanjeev2552 |
python
''' Program to shortest path from a given source vertex s to a given destination vertex t. Expected time complexity is O(V+E)''' from collections import defaultdict #This class represents a directed graph using adjacency list representation class Graph: def __init__( self ,vertices): self .V = vertices #No. of vertices self .V_org = vertices self .graph = defaultdict( list ) # default dictionary to store graph # function to add an edge to graph def addEdge( self ,u,v,w): if w = = 1 : self .graph[u].append(v) else : '''split all edges of weight 2 into two edges of weight 1 each. The intermediate vertex number is maximum vertex number + 1, that is V.''' self .graph[u].append( self .V) self .graph[ self .V].append(v) self .V = self .V + 1 # To print the shortest path stored in parent[] def printPath( self , parent, j): Path_len = 1 if parent[j] = = - 1 and j < self .V_org : #Base Case : If j is source print j, return 0 # when parent[-1] then path length = 0 l = self .printPath(parent , parent[j]) #increment path length Path_len = l + Path_len # print node only if its less than original node length. # i.e do not print any new node that has been added later if j < self .V_org : print j, return Path_len ''' This function mainly does BFS and prints the shortest path from src to dest. It is assumed that weight of every edge is 1''' def findShortestPath( self ,src, dest): # Mark all the vertices as not visited # Initialize parent[] and visited[] visited = [ False ] * ( self .V) parent = [ - 1 ] * ( self .V) # Create a queue for BFS queue = [] # Mark the source node as visited and enqueue it queue.append(src) visited[src] = True while queue : # Dequeue a vertex from queue s = queue.pop( 0 ) # if s = dest then print the path and return if s = = dest: return self .printPath(parent, s) # Get all adjacent vertices of the dequeued vertex s # If a adjacent has not been visited, then mark it # visited and enqueue it for i in self .graph[s]: if visited[i] = = False : queue.append(i) visited[i] = True parent[i] = s # Create a graph given in the above diagram g = Graph( 4 ) g.addEdge( 0 , 1 , 2 ) g.addEdge( 0 , 2 , 2 ) g.addEdge( 1 , 2 , 1 ) g.addEdge( 1 , 3 , 1 ) g.addEdge( 2 , 0 , 1 ) g.addEdge( 2 , 3 , 2 ) g.addEdge( 3 , 3 , 2 ) src = 0 ; dest = 3 print ( "Shortest Path between %d and %d is " % (src, dest)), l = g.findShortestPath(src, dest) print ( "Shortest Distance between %d and %d is %d " % (src, dest, l)), #This code is contributed by Neelam Yadav |
C#
// C# to shortest path from a given source vertex 's' to // a given destination vertex 't'. Expected time complexity // is O(V+E). using System; using System.Collections.Generic; class GFG { // This class represents a directed graph using adjacency // list representation class Graph { public int V; // No. of vertices public List< int >[] adj; // No. of vertices static int level; // Constructor public Graph( int V) { this .V = V; this .adj = new List< int >[2 * V]; for ( int i = 0; i < 2 * V; i++) this .adj[i] = new List< int >(); } // adds an edge public void addEdge( int v, int w, int weight) { // split all edges of weight 2 into two // edges of weight 1 each. The intermediate // vertex number is maximum vertex number + 1, // that is V. if (weight == 2) { adj[v].Add(v + this .V); adj[v + this .V].Add(w); } else // Weight is 1 adj[v].Add(w); // Add w to v's list. } // print shortest path from a source vertex 's' to // destination vertex 'd'. public int printShortestPath( int [] parent, int s, int d) { level = 0; // If we reached root of shortest path tree if (parent[s] == -1) { Console.Write( "Shortest Path between" + "{0} and {1} is {2} " , s, d, s); return level; } printShortestPath(parent, parent[s], d); level++; if (s < this .V) Console.Write( "{0} " , s); return level; } // finds shortest path from source vertex 's' to // destination vertex 'd'. // This function mainly does BFS and prints the // shortest path from src to dest. It is assumed // that weight of every edge is 1 public int findShortestPath( int src, int dest) { bool [] visited = new bool [2 * this .V]; int [] parent = new int [2 * this .V]; // Initialize parent[] and visited[] for ( int i = 0; i < 2 * this .V; i++) { visited[i] = false ; parent[i] = -1; } // Create a queue for BFS List< int > queue = new List< int >(); // Mark the current node as visited and enqueue it visited[src] = true ; queue.Add(src); while (queue.Count != 0) { // Dequeue a vertex from queue and print it int s = queue[0]; if (s == dest) return printShortestPath(parent, s, dest); queue.RemoveAt(0); // Get all adjacent vertices of the dequeued vertex s // If a adjacent has not been visited, then mark it // visited and enqueue it foreach ( int i in this .adj[s]) { if (!visited[i]) { visited[i] = true ; queue.Add(i); parent[i] = s; } } } return 0; } } // Driver Code public static void Main(String[] args) { // Create a graph given in the above diagram int V = 4; Graph g = new Graph(V); g.addEdge(0, 1, 2); g.addEdge(0, 2, 2); g.addEdge(1, 2, 1); g.addEdge(1, 3, 1); g.addEdge(2, 0, 1); g.addEdge(2, 3, 2); g.addEdge(3, 3, 2); int src = 0, dest = 3; Console.Write( "Shortest Distance between" + " {0} and {1} is {2}" , src, dest, g.findShortestPath(src, dest)); } } // This code is contributed by PrinciRaj1992 |
输出：
Shortest Path between 0 and 3 is 0 1 3 Shortest Distance between 0 and 3 is 3
这种方法是如何实现O（V+E）的？在最坏的情况下，所有边的权重都是2，我们需要执行O（E）操作来分割所有边和2V顶点，因此时间复杂度变成O（E）+O（V+E），也就是O（V+E）。
本文由 阿迪蒂亚·戈尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
