COMP2011 Tutorial Exercises, Week 10

Graph Traversal, Minimum Spanning Tree

Tutorial Questions

  1. Dijkstra's Algorithm (G&T Chap 13)

    Trace through the steps of Dijkstra's Algorithm, applied to the following weighted graph (starting from vertex "A"). Show the order in which the vertices are removed from the priority queue and added to the "cloud", and the distance estimates as they are updated for each vertex.

  2. Shortest Paths (G&T Chap 13)

    C-12.15 Give an example of a weighted directed graph with negative-weight edges, but no negative-weight cycle, such that Dijkstra's algorithm incorrectly computes the shortest-path distances from some start vertex.

  3. Diameter of a tree

    Given a free tree T, the diameter of T is the length of a longest path between two nodes of T.

    a) Give an efficient algorith for computing the diameter of T (assuming all edges are weighted equally).
    b) What if the edges are weighted unequally?

  4. Any Questions about Assignment 3.