Implementation of Dijkstra's Shortest Path Algorithm Using Arrays


Added on  2019-09-30

4 Pages1819 Words204 Views
TitleDepartment name, College name with full addressYour email addressAbstract—Nowadays, in computer networks, the routing is based on the shortest path problem. This will help in minimizing the overall costs of setting up computer networks. New technologies such as map-related systems are also applying the shortest path problem. Thispaper’s main objective is to evaluate the Dijkstra’s Algorithm n solving the shortest path problem.I. INTRODUCTIONTHE shortest path problem is a problem of finding the shortestpath or route from a starting point to a final destination.Generally, in order to represent the shortest path problem we usegraphs. A graph is a mathematical abstract object, whichcontains sets of vertices and edges. Edges connect pairs ofvertices. Along the edges of a graph it is possible to walk bymoving from one vertex to other vertices. Depending onwhether or not one can walk along the edges by both sides or byonly one side determines if the graph is a directed graph or anundirected graph. In addition, lengths of edges are often calledweights, and the weights are normally used for calculating theshortest path from one point to another point. In the real world itis possible to apply the graph theory to different types ofscenarios. For example, in order to represent a map we can use agraph, where vertices represent cities and edges represent routesthat connect the cities. If routes are one-way then the graph willbe directed; otherwise, it will be undirected. There existdifferent types of algorithms that solve the shortest pathproblem. However, only several of the most popularconventional shortest path algorithms along with one that usesgenetic algorithm are going to be discussed in this paper, andthey are as follows:1. Dijkstra’s AlgorithmII. MOTIVATIONTo determine and identify the concepts of the shortestpath problem. To determine the representation of graphs in computerin order to solve the shortest path problem, as well as tounderstand the different basic terms of a graph.To explain the general concepts and theimplementations of Dijkstra’s Algorithm.To evaluate each algorithm, and presents theevaluations’ results.III. PROBLEM STATEMENTCalculate shortest path and alternative path(Re-routing) fromsource to destination considering distance and fare.There are two cities as Source and Destination. To travel fromSource city to Destination city we need to pass many cities orhighways. We are considering multiple cities in between and various waysto reach destination from source. There are two parameters to be considered in this case. We are considering distance and fare from source to destination.If a bus passenger wants to travel from Source to destination hecan select any route or any price. Price is irrespective to the distance. If any city or a node isneglected, then program should be able to display the shortestpath without considering that node
Implementation of Dijkstra's Shortest Path Algorithm Using Arrays_1

Tasks involved:1. Calculate and display the Shortest Distance from source node to destination2. Calculate and display the fare from source to destination3. Ask user to provide an input variable to remove any node from nodes available between source and destination excluding those two.4. Calculate and display new shortest route and fare5. Print a statement “Paths and fares other than the shortest path”6. Display all the possible paths and fare from source todestination other than the shortest path displayed aboveIV. LITERATURE REVIEWAs mentioned earlier, a graph can be used to represent a mapwhere the cities are represented by vertices and the routes orroads are represented by edges within the graph. In this section,a graph representation of a map is explained further, and briefdescriptions and implementations of the four shortest pathalgorithms being studied are presented.Representation of the GraphIn order to represent a graph in a computer we will useadjacency matrix a. The dimension of the matrix will be equal to(n x n), where n is number of vertices in graph. The element ofmatrix a[i][j] is identified by an edge that connects the i-th and j-th vertices; the value here represents the weight of thecorresponding edge. However, if there is no edge betweenvertices i and j, the value in (a[i][j]) will be equal to infinity. Anarray of edges is another common representation of the graph. Ifm is the number of edges in a graph, then in order to representthe graph we have to use m x 3 twodimensional arrays; in eachrow, the first vertex, the second vertex, and the edge thatconnects them are also stored. The benefit of using an array ofedges in comparison to adjacency matrix is when there is morethan one edge that connects two vertices we cannot useadjacency matrix in order to represent graph.V. SOLUTION/APPROACHDijkstra’s Algorithm:Explanation and Implementation For each vertex within a graphwe assign a label that determines the minimal length from thestarting point s to other vertices v of the graph. In a computer wecan do it by declaring an array d[]. The algorithm workssequentially, and in each step it tries to decrease the value of thelabel of the vertices. The algorithm stops when all vertices havebeen visited. The label at the starting point s is equal to zero(d[s]=0); however, labels in other vertices v are equal to infinity(d[v]=∞), which means that the length from the starting point sto other vertices is unknown. In a computer we can just use avery big number in order to represent infinity. In addition, foreach vertex v we have to identify whether it has been visited ornot. In order to do that, we declare an array of Boolean typecalled u[v], where initially, all vertices are assigned as unvisited(u[v] = false). The Dijkstra’s algorithm consists of n iterations.If all vertices have been visited, then the algorithm finishes;otherwise, from the list of unvisited vertices we have to choosethe vertex which has the minimum (smallest) value at its label(At the beginning, we will choose a starting point s). After that,we will consider all neighbors of this vertex (Neighbors of avertex are those vertices that have common edges with the initialvertex). For each unvisited neighbor we will consider a newlength, which is equal to the sum of the label’s value at theinitial vertex v (d[v]) and the length of edge l that connectsthem. If the resulting value is less than the value at the label,then we have to change the value in that label with the newlyobtained value d [ neighbors ] = min ( d [ neighbors ] , d[ v ] + l ) After considering all of the neighbors, we will assign the initialvertex as visited (u[v] = true). After repeating this step n times,all vertices of the graph will be visited and the algorithmfinishes or terminates. The vertices that are not connected withthe starting point will remain by being assigned to infinity. Inorder to restore the shortest path from the starting point to othervertices, we need to identify array p [], where for each vertex,where v ≠ s, we will store the number of vertex p[v], whichpenultimate vertices in the shortest path. In other words, acomplete path from s to v is equal to the following statement P = ( s , ... , p [ p [ p [ v ] ] ] , p [ p [ v ] ] , p [ v ] , v )
Implementation of Dijkstra's Shortest Path Algorithm Using Arrays_2

End of preview

Want to access all the pages? Upload your documents or become a member.

Related Documents
Surname: 1 Student’s Name: Professor’s Name Course Name: Date:

SIT221 Assignment for Data Structure and Algorithms.

Bellman-Ford and Kruskal’s algorithm

A-Star Algorithm: Pathfinding Algorithm for Finding Shortest Path

Assignment about Corona Epidemic

Discrete Mathematics