CS 502 Fundamental of Algorithms
Assignment # 04
Spring 2012
Total Marks = 20
Deadline
Your assignment must be uploaded / submitted before or on June 19, 2012
Upload Instructions
Please view the assignment submission process document provided to you by the
Virtual University.
Rules for Marking
Please note that your assignment will not be graded if:
• It is submitted after due date
• The file you uploaded does not open
• The file you uploaded is copied from someone else or from internet
• It is in some format other than .doc
Note: Material that is an exact copy from handouts or internet would be graded
Zero marks. Your solution should consist of the material found through different sources and written in your own words.
Assignment Statements:
Question:
Give an example of a directed graph G = (V, E), a source vertex s 
V, and a set of tree edges Eπ ⊆ E such that for each vertex v V, the unique path in the graph (V, Eπ) from s to v is a shortest path in G, yet the set of edges Eπ cannot be produced by running BFS on G, no matter how the vertices are ordered in each adjacency list.
V, and a set of tree edges Eπ ⊆ E such that for each vertex v V, the unique path in the graph (V, Eπ) from s to v is a shortest path in G, yet the set of edges Eπ cannot be produced by running BFS on G, no matter how the vertices are ordered in each adjacency list.
No comments:
Post a Comment