DYNAMIC PROGRAMMING METHOD USING FORMULATING TECHNIQUE TO SOLVE SOME TYPICAL PROBLEM IN GRAPH THEORY

Abstract

Dynamic programming has been proven to be an effective method to solve class of optimization problems in the recent years. The study of specific techniques of dynamic programming to solve optimization problems is a really necessary issue. In this paper, we present a dynamic programming method using formulating technique to solve some typical problems in graph theory. Detailed steps of formulating technique have been studied and synthesized to effectively solve a class of typical problems in graph theory. The analysis in oder to select suitable data structure and establish the optimal formula to effectively solve the problem is also presented. Besides, the experiments using python programming language has been conducted for visualizing the results of dynamic programing method with three typical problems in graph theory: shortest path finding, minimum spanning tree finding, maximum network flow finding. The obtained results show that the dynamic programming method using the formulating technique helps to solve some typical problems of graph theory effectively.