The Northern Sea Route (NSR) links the Atlantic and Pacific oceans through the Arctic and it is critical for global trade as it provides a route between Asia and Europe that is significantly shorter than the alternatives. NSR is soon expected to open for intercontinental shipping due to global warming and thus presents tremendous opportunities for reductions in shipping time, cost, and environmental impacts. On the other hand, facilitating this route requires innovative approaches due to the navigation risks associated with its ice-covered waters. This study presents a graph-theoretical approach for optimal naval navigation in ice-covered sea routes with flexible turn angles based on the idea of large-adjacency grid graphs. Our model allows for asymmetric left and right turn radii as well as turn speeds that vary as a function of the turn angle and it offers natural-looking navigation paths.