©2000
Ting-Yuan Wang

Due date: next Friday (12/8) before noon

Problems: 

Implement the following Algorithms:

A. Kruskal's Minimum Spanning Tree (MST) Algorithm

B. Prime's Minimum Spanning Tree (MST) Algorithm

C. Dijkstra's Shortest-Path Algorithm

Description:

1. Your program should be able to read the input files and generate the output file with filename "output.txt". Please follow the procedure shown below.

>> MST                <---- your program name

Input file: XXXXX   <--- read the input file XXXXX

======== ECE902 Homework 6 ========

Algorithms:

    1. Kruskal's MST Algoritm
    2. Prime's MST Algorithm
    3. Dijkstra's Shortest-Path Algorithm

============================

Choose the method: 

2. The sample input file format is as follows:

===================================
The format of input file is an adjacency-list representation.

9    ======> Total # of nodes
1 -> (2,4) -> (8,8)  ===> node 1 connects to node 2 and 8 with cost 4 and 8, respectively. e.x. (2,4) means node 1 connects to node 2 with cost 4.
2 -> (1,4) -> (3,8) -> (8,11)
3 -> (2,8) -> (4,7) -> (6,4) -> (9,2)
4 -> (3,7) -> (5,9) -> (6,14)
5 -> (4,9) -> (6,10)
6 -> (3,4) -> (4,14) -> (5,10) -> (7,2)
7 -> (6,2) -> (8,1) -> (9,6)
8 -> (1,8) -> (2,11) -> (7,1) -> (9,7)
9 -> (3,2) -> (7,6) -> (8,7)

===================================

The graph of the sample file is shown in CLR textbook p.506.

3. For the output file, show the minimum value and the arcs chosen. For the expression of arcs, if you have a directed arc (i,j), which means the direction of the arc is from node i to node j. 

Requirements:

1. Write down about 2 pages of introduction and discussion sections.
2. Write down comments on your codes.
3. Follow the input and output files format.
4. It is very important that your codes can function correctly.
5. Make sure that your programs can be run on the Unix systems, and write down how to run them.

Submission:

    Please submit a paper version( before class )  and electronic version( by e-mail ) to TA.

[ Home ] [ News ] [ Lecture Outline ] [ Lecture Notes ] [ HomeWorks ] [ Project ] [ Quiz ] [ Miscellanea ]

Electrical and Computer Engineering ~ University of Wisconsin-Madison ~ 1415 Engineering Drive Madison, WI 53706-1691 ~ Tel: 608/262-3840 ~ Fax: 608/262-1267
Last modified: 11/22/00 02:42 PM by Ting-Yuan