A Line Graph-Based Model To Detect Optimal Routing Path in Decentralized Exchanges (DEXs)

Decentralized exchanges (DEXs), such as the CPMM-based Uniswap V2, are integral to the blockchain ecosystem, enabling token trading by exchanging a fixed amount of one token for the maximum possible amount of another. Despite active trading, research on optimal trading path identification remains limited. This paper introduces the line-graph-based algorithm (LG), which efficiently detects optimal trading paths in DEXs. Comparing LG with the commonly used Depth-First Search (DFS) algorithm under a linear routing scenario—including Uniswap, SushiSwap, PancakeSwap—reveals that LG identifies equally or more profitable paths while maintaining comparable gas costs. Tests from different perspectives on Uniswap V2 token graphs across two snapshots confirm its effectiveness. Although LG’s runtime grows exponentially with graph size in empirical tests, it remains competitive in real-world applications. These findings highlight LG’s strong potential for industrial adoption, benefiting traders and market participants.