Name
tsp
Synopsis
int tsp(List *vertices, const TspVertex *start, List *tour, int (*match) (const void *key1, const void *key2))
Return Value
0 if computing the approximate traveling-salesman tour is successful, or -1 otherwise.
Description
Computes an approximate traveling-salesman tour of the
points specified as vertices in
vertices. The tour begins at the vertex
specified by start. The operation
modifies vertices, so a copy should be
made before calling the operation, if necessary. Each element in
vertices must be of type
TspVertex. Use the
data member of each
TspVertex structure to store data
associated with the vertex, such as an identifier. Use the
x and y
members of the structure to specify the coordinates associated
with the vertex. The function specified by
match determines whether two vertices
match. It should only compare the data
members of TspVertex structures. The
tour is returned in tour, which is a
list of TspVertex structures. Each
vertex appears in tour in the order it
would be encountered during the tour. The elements in
tour point to the actual vertices in
vertices, so the caller must ensure
that the storage in vertices remains
valid as long as tour is being
accessed. Use list_destroy to destroy
tour once it is no longer
needed.
Complexity
O (V 2), where V is the number of vertices to visit in the tour.
Get Mastering Algorithms with C now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
