Greedy Graph Algorithms - Virginia Tech

Greedy Graph Algorithms

T. M. Murali September 16, 21, 23, and 28, 2009

T. M. Murali

September 16, 21, 23, and 28, 2009

CS 4104: Greedy Graph Algorithms

Shortest Path Problem

G (V , E ) is a connected directed graph. Each edge e has a length le 0. V has n nodes and E has m edges. Length of a path P is the sum of the lengths of the edges in P. Goal is to determine the shortest path from a specified start node s to each node in V . Aside: If G is undirected, convert to a directed graph by replacing each edge in G by two directed edges.

T. M. Murali

September 16, 21, 23, and 28, 2009

CS 4104: Greedy Graph Algorithms

Shortest Path Problem

G (V , E ) is a connected directed graph. Each edge e has a length le 0. V has n nodes and E has m edges. Length of a path P is the sum of the lengths of the edges in P. Goal is to determine the shortest path from a specified start node s to each node in V . Aside: If G is undirected, convert to a directed graph by replacing each edge in G by two directed edges.

Shortest Paths INSTANCE: A directed graph G (V , E ), a function l : E R+, and a node s V SOLUTION: A set {Pu, u V }, where Pu is the shortest path in G from s to u.

T. M. Murali

September 16, 21, 23, and 28, 2009

CS 4104: Greedy Graph Algorithms

Example of Dijkstra's Algorithm

T. M. Murali

September 16, 21, 23, and 28, 2009

CS 4104: Greedy Graph Algorithms

Dijkstra's Algorithm

Maintain a set S of explored nodes: for each node u S, we have determined the length d(u) of the shortest path from s to u. "Greedily" add a node v to S that is closest to s.

T. M. Murali

September 16, 21, 23, and 28, 2009

CS 4104: Greedy Graph Algorithms

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download