On the Number of Shortest Weighted Paths in a Triangular Grid

Benedek Nagy and Bashar Khassawneh
Additional contact information
Benedek Nagy: Department of Mathematics, Faculty of Arts and Sciences, Eastern Mediterranean University, North Cyprus, via Mersin 10, Famagusta 99450, Turkey
Bashar Khassawneh: Department of Mathematics, Faculty of Arts and Sciences, Eastern Mediterranean University, North Cyprus, via Mersin 10, Famagusta 99450, Turkey

Mathematics, 2020, vol. 8, issue 1, 1-16

Abstract: Counting the number of shortest paths in various graphs is an important and interesting combinatorial problem, especially in weighted graphs with various applications. We consider a specific infinite graph here, namely the honeycomb grid. Changing to its dual, the triangular grid, paths between triangle pixels (we abbreviate this term to trixels) are counted. The number of shortest weighted paths between any two trixels of the triangular grid is discussed. For each trixel, there are three different types of neighbor trixels, 1-, 2- and 3-neighbours, depending the Euclidean distance of their midpoints. When considering weighted distances, the positive values α , β and γ are assigned to the ‘steps’ to various neighbors. We gave formulae for the number of shortest weighted paths between any two trixels in various cases by the respective weight values. The results are nicely connected to various numbers well-known in combinatorics, e.g., to binomial coefficients and Fibonacci numbers.

Keywords: triangular grid; honeycomb network; weighted distance; chamfer distance; combinatorics; shortest weighted paths; path counting (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/1/118/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/1/118/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:1:p:118-:d:308069

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().