C++ Data Structures and Algorithm Design Principles

7. Graph Algorithms II

Learning Objectives

By the end of this chapter, you will be able to:

• Describe the inherent problems of Dijkstra's algorithm and demonstrate how it can be modified and/or combined with other algorithms to circumvent those issues
• Find the shortest path in a graph using the Bellman-Ford and Johnson's algorithms
• Describe the significance of strongly connected components in a garaph
• Use Kosaraju's algorithm to find strongly connected components in a graph
• Describe the difference between connectivity in directed and undirected graphs
• Implement depth-first search for complicated problems
• Evaluate negative weight cycles in a graph

This chapter builds upon the previous chapter by introducing some more advanced algorithms ...