Do you think IIT Guwahati certified course can help you in your career?
Introduction
Hello Ninja, welcome back. We'll develop code to determine a weighted graph's shortest route where the weight is either 1 or 2. Considering that the weight is either 1 or 2, When there are two weights, we put a third edge between them to reduce each weight to one.
Here, we'll first go through how to make a graph before using BFS to build an array of nodes that have already been visited. We will build the route using the array of previously visited elements.
Representation in Graphs
The first step is to represent the graph in a fashion that can be computed. I'll stand for election on a neighbor list. Where a list of surrounding nodes will be kept on file for each node in the graph, code now.
from collections import defaultdict
class Graph:
def __init__(
own_choise,
):
Own_choise = xyz
# We had a list with a default dict mapped to each node.
own_choise.graph = defaultdict(list)
In this case, the graph variable has a default "dict" with nodes that map to a list of adjacent edges. However, we must develop a function to generate edges and keep track of lists for each. That mapping will be created using the code below. The Graph class contains all of the functionalities.
def addEdge(own_choise, initial_edge, all_final_edge, edge_weight):
if edge_weight == 1:
own_choise.graph[initial_edge].append(all_final_edge)
# If edge weight is 1, we immediately add it to the list of that neighbor's neighbors.
Else:
# If there is no edge weight, we will build another edge to create both.
own_choise.graph[initial_edge].append(own_choise.num)
# We are updating its neighbours and adding it as the last vertex.
own_choise.graph[own_choise.num].append(all_final_edge)
# Since there is now one extra vertex, we will increase the number of .
own_choise.num = 1
Assume that node four and node five have a weight's edge two.
We'll change it to 4 --(1)--> 6 --(1)--> 5 instead of 4 --(2)--> 5 so that each edge has weight 1.
We can use BFS to identify the shortest path in a graph, which is why we changed the edge weights from 2 to 1. If you are unfamiliar with the breadth-first search method, please review this article first.
Problem Statements
Find the Shortest Path in a Weighted Graph where the Weight of an Edge is 1 or 2.
To understand the problem we have to understand what is weight graph first.
Weight graph
Every edge in weighted graphs is assigned a value (called weight). It relates to a straightforward graph with weighted edges. The weights are often used to determine the graph's shortest route.
The graph shown above is a weighted graph, in which a weight is assigned to each edge.
In a weighted network, not every node must have a unique weight; some edges may have the same weights.
Now we have to find the shortest path between the provided source vertex and the specified destination vertex in a directed graph where each edge has a weight of either 1 or 2.
Example
Assume that node 4 and node 5 have an edge of weight 2.
4—(2)—>5
The change will be made to 4 --(1)--> 6 --(1)--> 5.
such that every edge is weighed 1.
We can use BFS to identify the shortest path in a graph, which is why we changed the edge weights from 2 to 1. Please go through this article first if you are unfamiliar with the breadth-first search method.
Intuition
In order to tackle the mentioned challenges in O(N+M) time, we are seeking for a technique to improve the BFS approach, which finds the single source shortest routes in an unweighted directed graph. the number of edges is M, and the number of vertices is N.
The graph's vertices with an edge weight of 0 between them can be contracted, for example. But doing so would be incorrect since it would alter the graph's characteristics and introduce new edges to vertices that didn't previously have any.
In order to maintain a deque rather than a queue, utilize bfs with minor changes and put a vertex to the front of the deque if 0 edges are used and to the rear of the deque in all other cases.
Shortest path
Each node's parent is saved in a separate array throughout the BFS where the index is the node, and The index's parent is the value at the index. This array will enable us to create the route.
Construct Path
We will begin with the destination index, go on to the prev[index] value as an index, and keep going until we locate the source. To receive the output, we shall add to the route while performing.
Python Implementation
# importing defaultdict
from collections import defaultdict
class Graph:
# taking
def __init__(own_choise, numall_final_edge):
own_choise.numall_final_edge = numall_final_edge
own_choise.graph = defaultdict(list)
def addEdge(own_choise, initial_edge, edge_end, edge_weight):
if edge_weight == 1: # assigning edge_weight as 1
own_choise.graph[initial_edge].append(edge_end)
else:
own_choise.graph[initial_edge].append(own_choise.numall_final_edge)
own_choise.graph[own_choise.numall_final_edge].append(edge_end)
own_choise.numall_final_edge += 1
def printGraph(own_choise): # function to print graph
for i in range(own_choise.numall_final_edge):
print(f"{i}--->{own_choise.graph[i]} ")
def shortestPath(own_choise, src, dest): # function for shortest path
visited = [False] * own_choise.numall_final_edge
queue = [src]
visited[src] = True
prev = [None for i in range(own_choise.numall_final_edge)]
while len(queue) != 0:
s = queue.pop(0)
for i in own_choise.graph[s]:
if visited[i] == False:
queue.append(i)
visited[i] = True
prev[i] = s
if i == dest:
# print(prev)
print(own_choise.ConstructPath(src, dest, prev))
# Printing the shortest path
# print("Found!!!")
break
# When we not found any path then print 'not found'.
# print("Not Found!!")
def ConstructPath(own_choise, src, dest, prev):
path = [dest]
index = prev[dest]
path.append(index)
count = len(prev)
while count > 0:
index = prev[index]
path.append(index)
count -= 1
if prev[index] == src:
path.append(prev[index])
path.reverse()
return "-->".join(map(str, path))
return "Not Found!"
if __name__ == '__main__':
# List of graph edges according to the figure above
g = Graph(7)
g.addEdge(0, 1, 1)
g.addEdge(1, 2, 2)
g.addEdge(1, 3, 1)
g.addEdge(2, 3, 1)
g.addEdge(3, 6, 1)
g.addEdge(0, 2, 2)
g.addEdge(0, 5, 1)
g.addEdge(5, 4, 2)
g.addEdge(4, 3, 2)
g.addEdge(4, 6, 1)
g.shortestPath(0, 6)
Output
0-->1-->3-->6
Complexity
Time complexity
O(V+E): The complexity of DFS is O(V+E), where V is the number of vertexes and E is the number of edges.
Reason: The time complexity changes to O(E) + O(V+E), which is O(V+E) since all edges are of weight 2, and we must do O(E) operations to separate all edges and 2V vertices.
Space Complexity
O(V): The Space complexity is O(V), where V is the number of vertexes.
Reason: In the worst situation, the stack may increase until it reaches the graph's size. Therefore, it represents the space complexity O(V).
How can the shortest path be determined in a weighted graph?
Using Dijkstra's Algorithm is one typical method for locating the shortest path in a weighted network. The Dijkstra algorithm determines the graph's shortest route between any two vertices. Additionally, it may be used to create a Shortest Path Tree, which will show the shortest route between each graph vertex (from a given source vertex).
What is the graph's shortest path?
Finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its individual edges is reduced is known as the "shortest path problem" in graph theory.
What do you mean by the directed graph in DSA's?
A directed graph is a collection of linked objects (referred to as vertices or nodes) where all of the edges are directed from one vertex to another. A directed network or digraph are other names for a directed graph.
What are storage structures for graphs?
DFS will identify a solution if one exists for a given finite search tree if the search tree is finite. Optimality: DFS is suboptimal, which means there are too many stages or costs involved in getting to the answer.
Does Depth-First Search identify the shortest route?
A data structure known as a graph may be defined as one that has information that is stored among several groups of connected edges (paths) and vertices (nodes). A collection of Nodes and Edges make up the graph data structure (N, E). Vertices and nodes must both be finite.
Conclusion
In this article, we have solved a Data Structure and Algorithm related problem from the topic Graph. Suppose you want to practice the same kind of practice. Click here.
The Coding Ninjas Software development career is for you if you're looking for a more in-depth study that goes beyond Data Structure and covers the most in-demand programming languages and skills today.
Do you have any queries about the Depth-First Search algorithm covered in this tutorial? If so, do post them in part below this page that is designated for comments.
Please refer to our guided pathways on Code studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses, and use the accessible sample exams and questions as a guide. For placement preparations, look at the interview experiences and interview package.
If you find any problems, please comment. We will love to answer your questions.
84+ registered