Wrapping Up the Project

Implement the logic to generate the solution graph and finish the project by rendering the solution on the HTML web page.

We'll cover the following

Introduction

To recap, in the previous lesson we created the graph that depicts the problem statement and rendered it on the HTML web page using vis.js. Now, we'll follow the steps mentioned below and complete the project:

  1. Create the adjacency list for the graph and apply Dijkstra's algorithm to find the shortest route from the source city to the destination city.

  2. Handle the flight route scenario in which we can take a maximum of one flight route (edge) to reach the destination.

  3. Create the solution graph, which comprises a subset of the edges that denote the exact route that we should take in order to reach the destination.

  4. Merge all the functionalities and wrap up the project.

Create the adjacency list and handle the flight route scenario

Let's start by creating a function to perform the following steps:

  1. Create the adjacency list representation for the graph created for the problem statement.

  2. Apply Dijkstra's algorithm for two cases:

    1. To calculate the minimum distances from the source node to all other nodes. The distance array returned from this case will be used if we should travel from the source node to other nodes.

    2. To calculate the minimum distances from the destination node to all other nodes. The distance array returned from this case will be used if we should travel from the destination node to other nodes. Since all the edges are bi-directional, we can travel in the reverse direction as well in case this helps to minimize the total distance from the source to the destination.

  3. Handle the flight route scenario and check if the distance is minimized.

  4. Create a new directed graph representing the shortest possible route from the source node to the destination node.

Now let's move on to the code:

Get hands-on with 1200+ tech skills courses.