DEV Community

Cover image for Reduction of environmental pollution caused through vehicles using Graph theory
Mohammed Ashfaq Ashar for Mozilla Club of UCSC

Posted on

Reduction of environmental pollution caused through vehicles using Graph theory


In this modern era, vehicles are heavily used in all developed and non-developed countries. Day by day, usage of vehicles increased. So it causes several adverse effects to nature. One of the worst effects is Air pollution. Exhaust from vehicles is a significant wellspring of open-air contamination around the world
We simply called the pollution caused by the vehicle “vehicle pollutions”. Vehicular contamination is the presentation of unsafe material into the climate by engine vehicles. These materials, known as contaminations, have a few awful impacts on human wellbeing and the biological system. Transportation is a significant wellspring of air contamination in numerous nations throughout the planet because of the great number of vehicles that are accessible on the streets today. An expansion in buying power implies that more individuals would now be able to manage the cost of vehicles, which is awful for the climate. The air contamination from vehicles in metropolitan territories, especially in large urban areas, has become a major issue. The contamination from vehicles has started to tell through indications like severe cough like asthma, migraine, queasiness, disturbance of eyes, different bronchial and perceivability issues.
Ozone, Particulate matter, Nitrogen oxides, Carbon monoxide, Sulphur dioxide, and hazardous air pollutants are some of the main ingredients of vehicular pollutions.
Due to above such mentioned issues, there is a very simple and clear solution for it. Dijkstra's Algorithm is coming under graph theory that is normally used to find the shortest path between two points.
By applying this practical solution, to this problem, we are successfully able to get rid of these issues. Overall, we can observe that problem is mainly due to the traveling of vehicles worldwide without having a proper and shorter path to reach the destination. So due to it, there will wastage of fuels at the same time, pollutants are released to the environment. By having a shortest between the starting point and ending point, we could able to minimize these issues. Therefore Dijkstra's Algorithm helps us to solve this issue. This algorithm continuously go through all the possible path and get the best shortest path between two points which helps to preserve fuels and minimize the release of pollutants
Alt Text


In this article, Dijkstra's Algorithm has been used to solve the problem that has already been mentioned. If the vehicles traveled so long without any proper and shortest route rather than regular route, there are high chances of getting pollution. The shortest routing helps for the least pollution.

Alt Text
The following model represents a simple road network model
with starting point and ending point

G = (V, E) as per the definition of a graph. “V” represents a set of vertices and “E” represents a set of edges. So the road network has to mapped to graph inorder to have the least pollution to environment and also preserve the fuels. Therefore vertices, we simply say nodes are compared to cities, and edges were compared to road. And also the values that written on top of the edges are simply said as “weights” according to graph theory. Therefore such graphs are considered to be weighted graphs. These weights are considered the distance between two cities.

For example, we simply set “C” (red dot) as a starting node. Therefore we make as distance 0 while others to infinity as step 1
Alt Text

Then we can see the neighbor nodes of “C” which are “A”, “B” and “D”. Since “C” is starting node, the weights of “A”, “B” and “D” as follows
A = 0 + 1 = 1
B = 0 + 7 = 7
C = 0 + 2 = 2

So now we can observe the shortest path among all the “A”, “B” and “D” is “A” where C – A is 1.
So now the red dot moves to “A”. from “A”, it is observable that only “B” is neighbor since “C” already visited. Therefore the new weight of “B” is 1 + 3 = 4 which is less than the previous 7.

Alt Text

As a result, we could recursively perform the same procedure inorder to get the least path or weight for all the vertices. The final result would be as follows

Alt Text

so the above weights which are compared with distances are given at top of nodes by taking “C” as a starting point. Inorder to clarify further, we could see on top of “B”, there is a number 4, which represents the shortest path from “C”, where “B” is the final destination. This means the path is, C A to B is1+3=4
But if we consider a path as
C to D to E to B which is 2+7+1=10 which is much more long compared to previous, where there will high wastage of fuels and a high amount of pollutants emission to the environment. Therefore Dijkstra's Algorithm solves this problem by finding the shortest path from starting point to all other points in order to reach the final destination with the least pollutants released to the environment.


In this article using the concept of graph theory which is Dijkstra's Algorithm, we tried to solve the problem caused due to unnecessary routes used to reach the final destination which results in environmental pollutions and high fuel consumption.
Therefore as a responsible individual, it is a must to protect nature and preserve fossil fuels for the future generation

Top comments (0)