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 v_{1}. 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.