Program for traversing a directed graph through DFS, visiting only vertices reachable from start vertex.

Question

Given a graph and a source node and destination node, find the number of shortest paths present between source and destination?

Answer 1

Input: A graph G and a vertex v of G
Output: All vertices reachable from v labeled as discovered

A recursive implementation of DFS:

1  procedure DFS(G,v):
2      label v as discovered
3      for all edges from v to w in G.adjacentEdges(v) do
4          if vertex w is not labeled as discovered then
5              recursively call DFS(G,w)

A non-recursive implementation of DFS:

1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5            v = S.pop()
6            if v is not labeled as discovered:
7                label v as discovered
8                for all edges from v to w in G.adjacentEdges(v) do
9                    S.push(w)

Source: https://en.wikipedia.org/wiki/Depth-first_search