In this paper we investigate a new approach for extracting features from a texture using Dijkstra's algorithm. The method maps images into graphs and gray level differences into transition costs. Texture is measured over the whole image comparing the costs found by Dijkstra's algorithm with the geometric distance of the pixels. In addition, we compare and combine our new strategy with a previous method for describing textures based on Dijkstra's algorithm. For each set of features, a support vector machine (SVM) is trained. The set of classifiers is then combined by weighted sum rule. Combining the proposed set of features with the well-known local binary patterns and local ternary patterns boosts performance. To assess the performance of our approach, we test it using six medical datasets representing different image classification problems. Tests demonstrate that our approach outperforms the performance of standard methods presented in the literature. All source code for the approaches tested in this paper will be available at: http://www.dei.unipd.it/node/2357.