Complex fuzzy sets (CFSs) are efficient tool to handle the uncertainties present in real-world complex-valued physical quantities and have become a prominent research topic in fuzzy set theory. The CFS is used to handle information about uncertainty and periodicity simultaneously in decision-making problem under complex environment. The aim of this research is to establish the innovative concept of complex Fermatean fuzzy graph (CFFG) and its scope of application in network optimization problems. CFFG is a generalization of a complex Pythagorean fuzzy graph (CPyFG) that is used to handle the vagueness with the degrees whose ranges are enlarged from real to complex subset with unit disc. In this paper, we studied a complex Fermatean fuzzy shortest path problem (CFFSPP) where the edge weights of the graph take complex Fermatean fuzzy numbers (CFFN) instead of real numbers. We developed a generalized Dijkstra’s algorithm using the existing arithmetic operation and improved score function of CFFN to find the shortest path. A numerical example is discussed to showcase the potency of the proposed algorithm.