Abstract: The chance that a man will develop lung cancer in his lifetime is about 1 in 14 and for a woman, the risk is about 1 in 17. The lung cancer can be cured only by the surgery alone in the early stage, no chemotherapy or radiation therapy is needed. There are cases where chemotherapy does not work in the stage 4. The shortest path in Protein-Protein Interaction (PPI) plays a vital role in identifying the cancer at an early stage. The identification of the cancer gene in the PPI is prolonged. This study proposed the improved bellman ford which is the optimized and efficient way to find the shortest path in the PPI network. PPI is constructed by obtaining the data from the Search Tool for the Retrieval of Interacting Genes/Proteins (STRING) and Kyoto Encyclopedia of Genes and Genomes (KEGG) database.