13 docs tagged with "graph"

In the applications described below we will assume that the graph is undirected.

Finding a shortest path between two nodes of a graph is an important problem that has many practical applications. For example, a natural problem related to a road network is to calculate the shortest possible length of a route between two cities, given the lengths of the roads.

The Bellman–Ford algorithm finds shortest paths from a starting node to all nodes of the graph. The algorithm can process all kinds of graphs, provided that the graph does not contain a cycle with negative length. If the graph contains a negative cycle, the algorithm can detect this.

Breadth-first search (BFS) visits the nodes of a graph in increasing order of their distance from the starting node. Thus, we can calculate the distance from the starting node to all other nodes using breadth-first search. However, breadth-first search is more difficult to implement than depth-first search.

Depth-first search (DFS) is a straightforward graph traversal technique. The algorithm begins at a starting node and proceeds to all other nodes that are reachable from the starting node using the edges of the graph.

Dijkstra’s algorithm finds shortest paths from the starting node to all nodes of the graph, like the Bellman–Ford algorithm. The benefit of Dijkstra’s algorithm is that it is more efficient and can be used for processing large graphs. However, the algorithm requires that there are no negative weight edges in the graph.

Using dynamic programming, we can efficiently answer many questions regarding paths in directed acyclic graphs. Examples of such questions are:

The Floyd–Warshall algorithm provides an alternative way to approach the problem of finding shortest paths. It finds shortest paths between all node pairs of the graph in a single run.

There are three classical ways to represent a graph. The choice of a data structure depends on the size of the graph and the way the algorithm processes it.

In this course we will use variable n as number of nodes and variable m as number of edges.

What is a Graph?

Algorithm

| A graph and topological sort |