In this video, we'll discuss what paths are and how to find your way as it travels along the nodes and edges of the graph. Let's start with an example. For this example, we'll consider an edge weighted graph with no loops as shown here. Term edge weighted means the edges have weights. The weight of the edge I to J is 15. We can think of this graph as a small road network, where the nodes are cities, and the edge weights are highway distances between them. To walk, or traverse, through this graph we'll define what a walk is. A walk is an arbitrary sequence of nodes and edges that starts from some node and ends on some node. Here we can go from H to F to G to C to F to E to B. Notice that in this walk, we went through the node F twice. In many applications, we do not want to consider arbitrary walks but consider a walk where we do not repeat nodes unless we need to come back to the starting point. Such a constrained walk is called a path. The green arrows indicate a path from J to B. We said on the last slide that a path can start from a node and end on it. Such a path is called a cycle when the path has a three or more nodes. The J, G, C, F, J, is a four node cycle, sometimes called a four cycle. C, F, E is a three cycle. However, although there is an edge from F to J and another from J back to F, this two node path is not a cycle by our definition. A network with no cycles is called acyclic. A graph that is both directed and acyclic is called a directed acyclic graph, in short, a deck. A trail is a concept similar to a path, it is a walk with no repeating edges. In the graph shown in the walk, H, F, G, C, F, E, C, F, J, is not a trail. Because C, F Is traversed twice. Remember the seven bridges of the Konigsberg problem that we described in module one? In that problem, we had the constraint that one cannot cross the same bridge twice. Often we see such constraints in path planning problems. A common notion in directive graphs is called reachability. If there is a path from node U to node V, V is reachable from U. Reachability is not symmetric. Even if V is reachable from U, U may or may not be reachable from V. As we can see in this graph, I is not reachable from A. Look at A more carefully. There is no outgoing edge from A at all. So no node in this graph is reachable from A. A is a terminal, a leaf node of the graph. Where do we see this in real life? Think of road network with one way streets and road blocks through the construction. This can make some areas unreachable by cars. In biology, there are gene regulation networks, in which the nodes represent genes and edges represent the fact that gene A regulates gene B and not visa verse. This makes it a directed graph. We can easily think of a case where A regulates B, and B regulates C, but C does not regulate B or A. That's making A unreachable from C. The final concept you will explore in this graph, in this lecture, is that of a graph diameter. The diameter of a graph measures the maximum number of steps, also called hops, want us to traverse to go to the most distant node in the graph. That means, if you go from an arbitrary node to any other arbitrary node in the graph, following only the shortest paths roots, what is the maximum number of steps you have to take? Let's see how this is computed. For this task, we'll create a matrix called the shortest hop distance matrix. Just like the adjacency matrix, the rows and columns here represent graph nodes. And each cell contains the distance from the I eighth node, to the G eighth node via the shortest path. The distance from any node to itself is zero. So all diagonal elements of the matrix are zero. If a node I cannot reach node J through any path, the distance is marked as infinity. Thus, the distance from B to C is infinity. You can go from E to F in two steps, E to C to F. Therefore, the wait at the C cell is two. If you fill this matrix, you will notice that the largest reachable value is 4 in doing the infinite distance. Thus, the diameter of this graph is 4 where It represents the part from I to A, through J, G and D. There are a few noteworthy items in this Distance Matrix. The row of A has a value of 0 with itself and infinity for every other node. This happens because A is a leaf node. Similarly, except for the 0 distance with itself, the H column has infinity for all of the nodes. This happens because H has no incoming edges and therefore no other node can reach H.