Shady Fanous

Problem Statement The All-Pairs Shortest Paths (APSP) problem is generally defined as the following: Given a graph G, what is the shortest path between all pairs of vertices in G? Example: Given a city (graph) with junctions (vertices) and roads (edges), what is the shortest path from every junction in... [Read More]

Problem Statement The Single-Source Shortest Paths (SSSP) problem is generally defined as the following: Given a graph G and a source vertex s, what are the shortest paths from s to every other vertex in G? Example: Given a city (graph) with junctions (vertices) and roads (edges), what is the... [Read More]

Problem Statement Given a connected, undirected and weighted graph G, find a subset of the edges E such that G is still connected and the weight of the selected subset is minimal Example: Building a road network in a village such that each hut (vertex) is connected and the cost... [Read More]

Problem Statement Given a directed graph with V nodes and E edges, find, if any, its Strongly Connected Components (SCC) A SCC is defined as a sub-graph where for every pair of vertices u and v, there exists a path from u to v and from v to u. Example:... [Read More]

Problem Statement Given an undirected graph with V nodes and E edges, find a node v (called an Articulation Point or a Cut Vertex) or an edge e (Bridge) such that its removal would cause the graph to be disconnected. Example: Given a computer network, find a computer (node) whose... [Read More]

Problem Statement Given a graph with V vertices and E edges, sort the vertices so that for each directed edge, \(u \rightarrow v\), u comes before v in ordering. Examples Sorting a sequence of jobs or tasks based on their dependencies. Topological Sorting gives us an order in which to... [Read More]