Cluster of Optimal Chains of All-Pairs Shortest Paths to Deduce Minimum Cost Tour

Main Article Content

Govindaraj Pandith T.G
Dr. Siddappa M

Abstract

This paper aims at analyzing all-pairs shortest paths algorithm by Floyd to extract optimal path between any pair of vertices of various path length. To form least cost round tour, vertices of an optimal chain are grouped into cluster. These optimal chains are combined by taking an account of both path length as well as magnitude of the path. The chain which has largest path length and optimal distance will be considered first. Tour is constructed by adding up vertices to optimal chains in suitable positions based on nearness. This approach is a mix of both dynamic and greedy strategies. Illustrations of different variations are focus of the study.

Keywords:Cost Adjacency Matrix, Optimal Chain, Round tour, Path length matrix, predecessor matrix and all-pairs shortest paths

Downloads

Download data is not yet available.

Article Details

Section
Articles