topological sortingtopological sorting for directed acyclic graph (dagis linear ordering of vertices such that for every directed edge uvvertex comes before in the ordering topological sorting for graph is not possible if the graph is not dag for examplea topological sorting of the following graph is " there can be more than one topological sorting for graph for exampleanother topological sorting of the following graph is " the first vertex in topological sorting is always vertex with in-degree as ( vertex with no in-coming edgesalgorithm to find topological sortingin dfswe start from vertexwe first print it and then recursively call dfs for its adjacent vertices in topological sortingwe use temporary stack we don' print the vertex immediatelywe first recursively call topological sorting for all its adjacent verticesthen push it to stack finallyprint contents of stack note that vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so onare already in stack topological sorting vs depth first traversal (dfs)in dfswe print vertex and then recursively call dfs for its adjacent vertices in topological sortingwe need to print vertex before its adjacent vertices for examplein the given graphthe vertex ' should be printed before vertex ' 'but unlike dfsthe vertex ' should also be printed before vertex ' so topological sorting is different from dfs for examplea dfs of the shown graph is " "but it is not topological sorting dynamic programming the floyd warshall algorithm is for solving the all pairs shortest path problem the problem is to find shortest distances between every pair of vertices in given edge weighted directed graph exampleinputgraph[][{ inf }{inf inf}{infinf }{infinfinf which represents the following graph