There are several different algorithm to find the shortest path between two vertices in a wighted graph.
Some of them are explained below:
Dijkstra`s Algorithm:
Dijkstra’s algorithm is a greedy algorithm for finding the shortest path between a single source node and all other nodes in a weighted graph. It was developed by Edsger W. Dijkstra in 1956 and published three years later.
Travelling salesman problem:
The traveling salesman problem (TSP) is a well-known optimization problem in graph theory that involves finding the shortest possible route that visits each city in a given list exactly once and returns to the starting city.
Nearest Neighbour Method:
The nearest neighbour algorithm was one of the first algorithms used to solve the travelling salesman problem approximately. In that problem, the salesman starts at a random city and repeatedly visits the nearest city until all have been visited.
This procedure gives reasonably good results for the travelling salesman problem.
The method is as follows:
Step1: Select an arbitrary vertex and find the vertex that is nearest to this starting vertex to form an initial path of one edge.
Step2: Let v denote the latest vertex that was added to the path. Now, among the result of the vertices that are not in the path, select the closest one to v and add the path, the edge-connecting v and this vertex. Repeat this step until all the vertices of graph G are included in the path.
Step3: Join starting vertex and the last vertex added by an edge and form the circuit.
Example: Use the nearest-neighbor method to solve the following travelling salesman problem, for the graph shown in fig starting at vertex v1.
Solution: We have to start with vertex v1. By using the nearest neighbor method, vertex by vertex construction of the tour or Hamiltonian circuit is shown in fig:
The total distance of this route is 18.
