kindly Read through abstracts,copy edith and give to your surpervisor....
PROJECT TOPIC: DESIGN AND IMPLEMENTATION OF ROAD NETWORK SYSTEM USING KRUSKAL ALGORITHM IN ROAD NETWORK
Department: Computer Science
FORMART: MS WORD
PAGES: 82 pages, abstract, chapter 1-5 , APENDIX A source code and APENDIX B output, well reserached and supervised
Get Complete Work
Transportation is an essential part of human activity which involves movement of people from one place to another and in many ways it forms the basis of all socio-economic interactions among users. Finding shortest part (route) most times become difficult to road users. The aim of this research is design and implementation road network using Kruskal algorithm in other to obtain shortest part on a road network. The proposed system was design using Java object oriented programming language and mysql database. The proposed system adopted is Dynamic Systems Development Model Methodology (DSDM). This paper looks at the existing road network in obio Akpor local government using information Technology in enhancing the network which will facilitate the finding of shortest path
1.1 Background of the study
Transportation is an essential part of human activity which involves movement of people from one place to another and in many ways it forms the basis of all socio-economic interactions. Indeed, no two locations will interact effectively without a viable means of transportation(Dr c. ugwu, 2014). In many developing countries, inadequate transport facilities are often the norm rather than the exception. Thus, a good transport system is essential to support economic growth and development. Since the attainment of independence in 1960, the problems of Nigerian transport system includes bad roads, inadequate fleets of buses or trucks, inadequate and overcrowded trains and airplanes and congested ports. These are common features of developing countries. In line with these are physical problems such as dearth of suitably-trained transport managers and planners, capital restructuring bottlenecks, serious issues of institutional reforms and ineffective traffic regulations. The transportation industry facilitates the movement of people and goods for the purposes of trade, production and consumption. Good transportation systems are often described as satisfying several quality factors, such as cost and time. These transport networks are used during the delivery of electoral materials in all the Local Government Areas and States in Nigeria. These electoral materials include ballot papers, ballot boxes, handbooks, images, registers, information and promotion, training materials, election posters, electoral forms, code of conduct etc.
In transportation network, graphs emerge naturally as a mathematical model of the observed real world system. Indeed, many problems can be reformulated as a quest for a path (between two nodes in a graph) which is optimal in the sense of a number of preset criteria. Very often, these optimality criteria are evaluated in terms of weights, that is, vectors of real numbers, associated with the links of the graph. Numerous algorithms have been developed to ease this and related quests. (Wiley, 1998) One of such algorithm is the minimum spanning tree algorithm which is a graph algorithm that finds the minimum path between paths in a network.
A spanning tree of a graph is a sub-graph that contains all the vertices of the graph but only enough of the edges to form a tree (Sedgwick 1989). Suppose G is an undirected graph, with weighted edges, and that G is connected, meaning that there is a path between any two distinct vertices of G, a tree T that contains all the vertices of G is called a spanning tree for G. We say that T spans all the vertices in G. If we define the cost of a spanning tree T to be the sum of the weights on its edges, we might then seek to find the spanning tree, T, of minimal cost that spans all the vertices in G. This is called a minimal spanning tree (Standish 1994).
This work is an example of a real life application of minimal spanning tree in graphs. Minimum spanning trees have been used in the design of electrical circuits, telephone networks, and bridge and road networks (Ahuja et al. 2003), and in the solution of the Traveling Salesman Problem (Papadimitriou and Vazirani 1984). They have also been used in clustering and some pattern analysis tasks (Niina 2005, Xu et al. 2002). Several efficient algorithms exist for finding minimal spanning tree in graphs, two of the most popular being Kruskal’s and Prim’s algorithms (Gabow et al. 1986, Pettie and Ramachandran 2000, Martel 2002, Czumaji et al. 2005, Haouari and Chaouachi 2006, Pop et al. 2006).
Kruskal's algorithm starts with each vertex in its own tree in a forest. The algorithm then considers each edge in turn, in order by increasing weight. If an edge (u, v) - linking vertices u and v - connects two different trees, then (u, v) is added to the set of edges of the MST, and the two trees connected by the edge are merged into a single tree. If, on the other hand, an edge (u, v) connects two vertices in the same tree, then edge (u, v) is discarded.
Prim’s algorithm, on the other hand, starts by picking any vertex v in G. It then finds the new vertex w that is connected to v by the edge of least distance; w and the edge e = (v,w) that connects them are then added to the minimal spanning tree T. The way it identifies which vertex to add to T is to choose that vertex w that is not already in the tree T such that the closest distance from w to some vertex in T is less than or equal to the closest distance of all the other vertices v that are not yet in T. It then adds to T both w and the edge of least distance connecting it to some vertex in T. It stops when T includes all vertices of G.
Road networks are observed in terms of its components of accessibility, connectivity, and traffic density, level of service, compactness, and density of particular roads. Level of service is a measure by which the quality of service on transportation devices or infrastructure is determined, and it is a holistic approach considering several factors regarded as measures of traffic density and congestion rather than overall speed of the journey (Mannering, Walter, and Scott, 2004).
Access to major roads provides relative advantages consequent upon which commercial users locate to enjoy the advantages. Modern businesses, industries, trades and general activities depend on transport and transport infrastructure, with movement of goods and services from place to place becoming vital and inseparable aspects of global and urban economic survival. Developments of various transportation modes have become pivotal to physical and economic developments.
Such modes include human porterage, railways, ropeways and cableways, pipelines, inland waterways, sea, air, and roads (Said and Shah, 2008).
According to Oyesiku (2002), urbanization in Nigeria has a long history in its Growth and development. Extensive development being a feature of the 19th and 20th centuries, with concentration of economic and administrative decision-making in Lagos, Ibadan, Kaduna, Jos, and Enugu, and high degree of specialization and larger population associated with greater specialization of goods and services. Wyatt (1997) states that urban areas have tendency to develop at nodal points in transport network and places with good road network will possess relative advantage over locations having poor network. Urban locations with such relative advantage are found where different transport routes converge with high degree of compactness, connectivity, density, length and accessibility exhibited within the intra- and inter- urban road networks.
1.2 Statement of the Problem
The relationship between transportation and urban property values has been the focus of many studies (for example, Dewees, 1976; Damm et al, 1980; Wolf, 1992; Singh, 2005). It was established that there was statistically significant relationship between distance of a parcel of land to the nearest Metro station and land price (Damm, Lerner-Lam, and Young, 1980), while there was evidence that residential property prices decrease immediately around the transport investment or station value uplift through changes in land values (Singh, 2005).
The urban areas all over the world offer a number of advantages in terms of concentration of people followed by demand for commercial properties and transportation. Ikeja is a classical example of a city that has developed rapidly since 1976 when it became the Lagos State capital. Construction of roads increased substantially with the opening up of residential precincts that also benefited from increasing demand for let table spaces in commercial properties. Many private companies, retail stores, commercial banks aggregate in the metropolis to take advantage of opportunities afforded by locations near the seat of governance thus attracting complimentary services. This led to high concentration of vehicular and pedestrian movements especially along the access roads.
The roads exhibit a number of nodes and linkages to form networks of both arterial and minor routes along which commercial properties locate. Commercial users displaced residential users, causing sites to be at highest and best uses with concomitant increases in the values of commercial properties. Accessibility within the road network is affected by the compact nature of various routes that sometimes impede volume of traffic. The road network is made up of nodal points and links that determine the degree of connectivity and accessibility in the network.
Poor road network has been identifying in Nigeria as one of the reason while people are locked up in traffics.