1. Home
  2. Docs
  3. Discrete Structure
  4. Graphs
  5. Shortest Path Problem

Shortest Path Problem

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.

WhatsApp Image 2023 09 28 at 14.22.34

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.

image 149

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.

image 144

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:

image 145

The total distance of this route is 18.

How can we help?

Leave a Reply

Your email address will not be published. Required fields are marked *