Skip to content

The purpose of this project is to solve the shortest path problem, one of the fundamental theoretic problems known in graph theory, and how Dijkstra's algorithm can be used to solve it. Done as part of the final project for MOOC on Graph Theory by UCSD.

License

Notifications You must be signed in to change notification settings

anandketan/Graphing_Flight_Paths

Repository files navigation

Flight Routes

Planning flight routes is done most effectively using graph theory where mathematical structures are used to model pairwise relations between destinations. A graph in this context is made up of vertices, also called nodes which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically.

Modelling airports as nodes and applying Dijkstra's algorithm to eliminate routes with excessive nodes, we can visualize the above problem as the network below:

flight_planning

Dijkstra's Algorithm

Dijkstra's algorithm allows us to find the shortest path between any two vertices of a graph. It differs from the minimum spanning tree because the shortest distance between two vertices might not include all the vertices of the graph. It involves starting with a weighted graph, choosing a starting vertex and assigning infinity path values to all other nodes.
Each vertex is visited and its path length updated. If the path length of the adjacent vertex is lesser than new path length, don't update it and avoid updating path lengths of already visited vertices. After each iteration, we pick the unvisited vertex with the least path length. Repeat until all the vertices have been visited and longer routes have been removed.

Kruskal's Algorithm

Kruskal's algorithm to find the minimum cost spanning tree uses the greedy approach. This algorithm treats the graph as a forest and every node it has as an individual tree:

  1. Remove all loops and parallel edges.
  2. Arrange all edges in their increasing order of weight.
  3. Add the edge which has the least weightage.

References

Algorithms for SPF in Graph Theory: https://www.tutorialspoint.com/graph_theory/index.htm
Dijkstra's algorithm: https://brilliant.org/wiki/dijkstras-short-path-finder/
Seven Bridges of Königsberg problem: https://mathworld.wolfram.com/KoenigsbergBridgeProblem.html
Graph Theory introduction: http://stanford.edu/~jolivier/305_refresher_notes/Basic_graph_theory_and_algorithms.pdf
Graph Theory certification: https://coursera.org/share/7295db0e23458e17d3c31c22961cef75

About

The purpose of this project is to solve the shortest path problem, one of the fundamental theoretic problems known in graph theory, and how Dijkstra's algorithm can be used to solve it. Done as part of the final project for MOOC on Graph Theory by UCSD.

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages