Problem The most commonly encountered problem associated with weighted graphs is of finding the shortest path between two given vertices. Let us consider the Air Route plan shown below. We just want to find the cheapest route from one city to another. The Airways charges passengers a fixed fare to travel between any two cities. These fares are shown in the figure. That is, the fare from Muscat to Suhar is OMR 50, from Suhar to Salalah is OMR 90, and so on. The edges are directed. They represent single-track airway routes, on which travel is permitted in only one direction. For example, you can go directly from Muscat to Suhar, but not from Suhar to Muscat. The problem is to find the shortest path which doesnt necessarily mean in terms of distance; it can also mean cheapest, fastest, or best route by some measure. Write a report to analyze the above problem and mention the type of methodology you will adopt as a solution to the problem. Which algorithm is best suited for this problem? And develop a program using the Java programming language to find the shortest path from a specified vertex

SUHAR ABU DHABI OMR 60 (C ? OMR 50 OMR 50 OMR 40 OMR 90 MUSCAT A OMR 80 OMR 20 OMR 70 SALALAH DUBAI