Graph Traversal
Depth First Search
Steps for DFS
Algorithm of Depth First Search for a Graph with Disconnected Edges.
We will have a graph which will have list of vertices and edges.
Shortest Path Algorithms
Dijkstra’s Algorithm
1). Create a set sptSet, which keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.
2). Assign a distance value to all vertices in the input graph. Assign distance value as 0 for the source vertex so that it is picked first and initialize all distance values as infinite.
3). While sptSet doesn’t include all vertices, perform below steps:
3.1). Pick a vertex V which is not there in sptSet and has minimum distance value.
3.1). Add V in sptSet.
3.3). Update distance value of all adjacent vertices of V. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex AV, if sum of distance value of V (from source) and weight of edge V-AV, is less than the distance value of AV, then update the distance value of AV.
To understand this, lets take an example.
1). We will start from node A. The shortest path from A to B is 1, A to C is 2, A to D or E or F is unknown, thats why we treat them as infinity. Since the shortest is from A to B, so we will select B.
2). Now we fill find the shortest from B. B to C is 1+1 thats 2, since C is already 2 (from A to C is 2), we will not change the value at 2. From B to D it will be 4 (3+1), from B ro E it will be 3 (1+2). Path to F is unknown, so it will be still infinity. The shortest path from B is towards C (with value 2), so we will select C.
3). We have selected C, the path from C to E would be 4 (2+2), but the shortest path till E has value 3, which is less than 4, so we are not going to change it. The path from C to D will be 3 (2+1), earlier shortest path till D was 4, which is greater than 3, so we will change it to 3. Path till F is still unknown, so we will keep it infinity. Now the shortest path is at both D and E, (with value 3), we will select D.
4). We have selected D, from D to E the shortest path would be 7 (4+3), buty since shortest path till E has a value 3, which is less than 7, so we will not change the value. From D to F shortest path would be 6 (3+3), since the shortest path till F was infinity, which is greater than 6, we will change the shortest path value at F to 6. We have visited A, C, C, D. Now only E and F are remaining, value at E is less, so we will select E.
5). From E to F the shortest path would be 6 (3+3), the shortest path at F was already 6, so we are not going to change the value.
6). So finally we have visited all the vertices's, all the shortest path from A to all the vertices's are mentioned in the above image. From A to B its 1, from A to D its 3, from A to F its 6, from A to C its 2 and from A to E its 3.
Let's take another example, with some negative values:
1). We will start from '1', the path from '1' to '2' is 2, '1' to '4' is 8. and from '1' to '3' is unknown, so we will keep it as infinity. '1' to '2' has the minimum value, so we will select vertex '2'.
2). '2' is only connected to '3', so we will find the shortest path, which would be 5 (3+2), but the vertex '3' has infinity, which is higher than 3, so we will change the value at '3' to 5. Now we will select '3', since it has the minimum value.
3). From '3' only vertex '4' is connected, which had value 7. But from '3' to '4' the value would be -1 (5 minus 6), since -1 is less than 8, we will change the value at vertex '4' to -1.
Let's take another example and use Dijkstra Algorithm to find the shortest path:
1). Let's start from the vertex '1', the shortest path from '1' to '4' is 1, from '1' to '2' is 2. The vertex '3' is not directly approachable from '1' so we assume the shortest path is infinity. Vertex '4' has shortest path (that's 1), so we will select '4'.
2). From '4' no edge is going out, so we will select next vertex. '2' has the lowest value so we will select it.
3). From '2' only the vertex '3' is connected, we will change the value at vertex '3' from infinity to 5 (2+3). Now since all the vertices's except 3 are selected, we will select 3.
4). From '3' only '4'is connected, we will change the value at 4 to -1 (5-6). We changed the value at '4' because the previous one (1) is greater than the new one (-1). We had already selected the vertex '4' and found the shortest path as 1. But now the shortest path is modified to -1. That means in the first place Dijkstra has given me a wrong result.
As per Dijkstra, the vertices's which are already selected and we found the shortest path, we don't need to update it. In case of negative edges it is getting updated, that's why Dijkstra Algorithm may not work perfectly in case of negative edges.
Bellman-Ford Algorithm
We need to first make list of edges. In our case it would be (d,b), (c,d), (a,c), (a,b).
1). Take the list of all edges and mark the distances of all the vertices's as infinity, keep the first one ('a' in our case) as zero. Now we need to go and relax the vertices's for v-1 times (where v is number of vertices's), in our case it will be three. Lets start with d to b, d is infinity and b is infinity, so the shortest path from d to b would be infinity plus infinity which is infinity. Now we take c to d, again since both have infinity, so the shortest path at d would be infinity. Now take a to c, it would be 0+2, which is 2, we will change the shortest path at c from infinity to 2. Now we take a to b, and change the shortest path at b from infinity to 1. We have relaxed the vertices's for 1st time.
2). We repeat the process again, from d to b the shortest path would be infinity (value at d) minus 6 (since the edge has negative value), this will gives infinity. But the value at b is 1, which is less than infinity, so we are not going to change it. Now we take c to d, the shortest path would be 2+3 which is 5, shortest path at d was infinity, we will change it to 5. Now we take a to c, which gives shortest path as 2, which is already 2, so we are not going to change it. Same is the case from a to b. We have relaxed the vertices's for 2nd time.
3). Again we will go from d to b, the shortest path would be 5-6, thats -1. The shortest path at b is 1, which is greater than -1, so we will change it to -1. Then we will go from c to d, a to c, a to b, but the values remain unchanged.
4). We have relaxed vertices's for 3rd time. (v-1).
Bellman-Ford fails if there is a negative cycle in the graph. Like in the below case b-c-d has a cycle and total value is 1 + 3 + (-6), which is -3.
- Its the process of visiting and exploring a graph for processing.
- In this we visit and explore each vertex and edge in a graph such that all the vertices's are explored exactly once.
- Visiting a node means selecting a node, where as exploring means exploring the children nodes of the node which we have visited.
- Its an algorithm for traversing trees and graphs.
- In BFS we start with the root node, explores all sibling nodes before moving on to the next level of siblings.
- Queue is the main data structure which is used while performing BFS.
- BFS is used as a crawlers in web-engines. It is the main algorithm which is used for indexing the web pages, it starts from the source page and follows all the links associated with that page. In this case each link is considered as a node in the graph.
- BFS is also used in GPS navigation to find the neighboring locations.
- BFS is also used in finding the shortest path
 |
| PC: Edureka |
Steps:
1). We choose 'a' as our initial node, and insert it in the queue.
2). We extract 'a' from the queue, and insert the child nodes of 'a', which are b and c.
3). Now since 'b' is the door of the queue, we remove 'b' and add its child nodes d and e in the queue.
4). We do it till the queue is not empty.
Breadth First Traversal (or Search) for a graph is similar to Breadth First Traversal of a tree. But unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a Boolean visited array.
Here is pseudo code for BFS:
Queue Q;
BFS(Graph G, Node s)
{
//initialize the Q with the root node.
Q.enqueue(s);
mark s as visited
while(Q is not empty)
{
//add all the child nodes of 's' as marked.
//extract 's' from queue and visit the child nodes.
v=Q.dequeue();
//process all the child nodes of v, stores its child nodes(w) in the queue to further visit its child nodes.
for all neighbors w of v in the Graph Graph
if(w is not visited)
Q.enqueue(w);
mark w as visited.
}
}
When we should and shouldn't use breadth first search?1). We choose 'a' as our initial node, and insert it in the queue.
2). We extract 'a' from the queue, and insert the child nodes of 'a', which are b and c.
3). Now since 'b' is the door of the queue, we remove 'b' and add its child nodes d and e in the queue.
4). We do it till the queue is not empty.
Breadth First Traversal (or Search) for a graph is similar to Breadth First Traversal of a tree. But unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a Boolean visited array.
Here is pseudo code for BFS:
Queue Q;
BFS(Graph G, Node s)
{
//initialize the Q with the root node.
Q.enqueue(s);
mark s as visited
while(Q is not empty)
{
//add all the child nodes of 's' as marked.
//extract 's' from queue and visit the child nodes.
v=Q.dequeue();
//process all the child nodes of v, stores its child nodes(w) in the queue to further visit its child nodes.
for all neighbors w of v in the Graph Graph
if(w is not visited)
Q.enqueue(w);
mark w as visited.
}
}
- Use BFS for finding the shortest path between two nodes in a tree or in an unweighted graph.
- Do not use BFS on a graph or a tree with a high branching factor, since all current nodes are in memory.
- Its also an algorithm for traversing trees and graphs.
- In DFS, we start at the root node and explores as far down the path as possible until we hit the end (leaf node), then backtracks to the node that was the most recent 'root' node and explores again.
- This recursive nature of DFS can be implemented using stacks.
- We pick a starting node and push all its adjacent nodes into a stack.
- Pop a node from stack to select the next node to visit and push all its adjacent nodes into a stack.
- Repeat this process until the stack is empty.
- However, ensure that the nodes that are visited are marked, this will prevent us from visiting the same node more than once or we may end up in an infinite loop.
- Use DFS if you exhaustively explore every possible path.
- Use DFS if you are looking for the longest path between two nodes or when backtracking is important.
- Do not use DFS on very deep (or infinitely deep) graphs, because you may hit the max recursion depth before you find what you're looking for.
Algorithm of Depth First Search for a Graph with Disconnected Edges.
We will have a graph which will have list of vertices and edges.
Shortest Path Algorithms
Dijkstra’s Algorithm
- In Dijkstra’s algorithm we maintain two sets, one set contains vertices included in shortest path tree, other set includes vertices not yet included in shortest path tree. At every step of the algorithm, we find a vertex which is in the other set (set of not yet included) and has a minimum distance from the source.
1). Create a set sptSet, which keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.
2). Assign a distance value to all vertices in the input graph. Assign distance value as 0 for the source vertex so that it is picked first and initialize all distance values as infinite.
3). While sptSet doesn’t include all vertices, perform below steps:
3.1). Pick a vertex V which is not there in sptSet and has minimum distance value.
3.1). Add V in sptSet.
3.3). Update distance value of all adjacent vertices of V. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex AV, if sum of distance value of V (from source) and weight of edge V-AV, is less than the distance value of AV, then update the distance value of AV.
To understand this, lets take an example.
1). We will start from node A. The shortest path from A to B is 1, A to C is 2, A to D or E or F is unknown, thats why we treat them as infinity. Since the shortest is from A to B, so we will select B.
2). Now we fill find the shortest from B. B to C is 1+1 thats 2, since C is already 2 (from A to C is 2), we will not change the value at 2. From B to D it will be 4 (3+1), from B ro E it will be 3 (1+2). Path to F is unknown, so it will be still infinity. The shortest path from B is towards C (with value 2), so we will select C.
3). We have selected C, the path from C to E would be 4 (2+2), but the shortest path till E has value 3, which is less than 4, so we are not going to change it. The path from C to D will be 3 (2+1), earlier shortest path till D was 4, which is greater than 3, so we will change it to 3. Path till F is still unknown, so we will keep it infinity. Now the shortest path is at both D and E, (with value 3), we will select D.
4). We have selected D, from D to E the shortest path would be 7 (4+3), buty since shortest path till E has a value 3, which is less than 7, so we will not change the value. From D to F shortest path would be 6 (3+3), since the shortest path till F was infinity, which is greater than 6, we will change the shortest path value at F to 6. We have visited A, C, C, D. Now only E and F are remaining, value at E is less, so we will select E.
5). From E to F the shortest path would be 6 (3+3), the shortest path at F was already 6, so we are not going to change the value.
6). So finally we have visited all the vertices's, all the shortest path from A to all the vertices's are mentioned in the above image. From A to B its 1, from A to D its 3, from A to F its 6, from A to C its 2 and from A to E its 3.
Let's take another example, with some negative values:
1). We will start from '1', the path from '1' to '2' is 2, '1' to '4' is 8. and from '1' to '3' is unknown, so we will keep it as infinity. '1' to '2' has the minimum value, so we will select vertex '2'.
2). '2' is only connected to '3', so we will find the shortest path, which would be 5 (3+2), but the vertex '3' has infinity, which is higher than 3, so we will change the value at '3' to 5. Now we will select '3', since it has the minimum value.
3). From '3' only vertex '4' is connected, which had value 7. But from '3' to '4' the value would be -1 (5 minus 6), since -1 is less than 8, we will change the value at vertex '4' to -1.
Let's take another example and use Dijkstra Algorithm to find the shortest path:
1). Let's start from the vertex '1', the shortest path from '1' to '4' is 1, from '1' to '2' is 2. The vertex '3' is not directly approachable from '1' so we assume the shortest path is infinity. Vertex '4' has shortest path (that's 1), so we will select '4'.
2). From '4' no edge is going out, so we will select next vertex. '2' has the lowest value so we will select it.
3). From '2' only the vertex '3' is connected, we will change the value at vertex '3' from infinity to 5 (2+3). Now since all the vertices's except 3 are selected, we will select 3.
4). From '3' only '4'is connected, we will change the value at 4 to -1 (5-6). We changed the value at '4' because the previous one (1) is greater than the new one (-1). We had already selected the vertex '4' and found the shortest path as 1. But now the shortest path is modified to -1. That means in the first place Dijkstra has given me a wrong result.
As per Dijkstra, the vertices's which are already selected and we found the shortest path, we don't need to update it. In case of negative edges it is getting updated, that's why Dijkstra Algorithm may not work perfectly in case of negative edges.
Bellman-Ford Algorithm
- As we have seen in above example that Dijkstra Algorithm not always find the shortest path in case of negative edges. Bellman-Ford always give correct result even in case of negative edges (though it has its own drawback).
- As Dijkstra says relax the vertices's only once, Bellman-Ford says we can relax vertices's for n number of times, so that we can get perfect shortest path to all the vertices's.
- In Bellman-Ford we make list of all the edges and go one relaxing them for v-1 times (where v is the number of vertices) after which we will surely get the shortest path to all the edges even in case of negative edges.
We need to first make list of edges. In our case it would be (d,b), (c,d), (a,c), (a,b).
1). Take the list of all edges and mark the distances of all the vertices's as infinity, keep the first one ('a' in our case) as zero. Now we need to go and relax the vertices's for v-1 times (where v is number of vertices's), in our case it will be three. Lets start with d to b, d is infinity and b is infinity, so the shortest path from d to b would be infinity plus infinity which is infinity. Now we take c to d, again since both have infinity, so the shortest path at d would be infinity. Now take a to c, it would be 0+2, which is 2, we will change the shortest path at c from infinity to 2. Now we take a to b, and change the shortest path at b from infinity to 1. We have relaxed the vertices's for 1st time.
2). We repeat the process again, from d to b the shortest path would be infinity (value at d) minus 6 (since the edge has negative value), this will gives infinity. But the value at b is 1, which is less than infinity, so we are not going to change it. Now we take c to d, the shortest path would be 2+3 which is 5, shortest path at d was infinity, we will change it to 5. Now we take a to c, which gives shortest path as 2, which is already 2, so we are not going to change it. Same is the case from a to b. We have relaxed the vertices's for 2nd time.
3). Again we will go from d to b, the shortest path would be 5-6, thats -1. The shortest path at b is 1, which is greater than -1, so we will change it to -1. Then we will go from c to d, a to c, a to b, but the values remain unchanged.
4). We have relaxed vertices's for 3rd time. (v-1).
Bellman-Ford fails if there is a negative cycle in the graph. Like in the below case b-c-d has a cycle and total value is 1 + 3 + (-6), which is -3.
-K Himaanshu Shuklaa..
No comments:
Post a Comment