(Please solve it using C language NOT C++)
Write a C program .. Traditional Dijkstra algorithm search for the shortest path from the source node to a distention node in a map with a single source.it's only finds one shortest path through searching and skip over other paths with the same distance.
.
.
Please take a look at these papers, may be its useful to you. (Please help??)
Path-planning of Automated Guided Vehicle based on Improved Dijkstra Algorithm Guo Oing, Zhang Zheng. Xu Yue College of Information Science and Technology, Beijing University of Chemical Technology, Beijing 100029 E-mail: gaoging@ mail.buct.odu.cn Abstract: In the automated storage and retrieval system (AS/RS), a reasonable path-planning is fundamental for the effective work of AGV. For the rectangular environment map of the AS RS system, the traditional Dijkstra algorithm can only find one shortest path, and skip over other paths with the same distance An mproved Dykstra algorithmus proposed to solve the path-planning problem in the rectangular environment, which can find all equidistant shortest paths. The optinal path with both the shortest distance and time is obtained by adding running time to the h planning evaluatin. The algorithm is programmed using Vismal C++, and the simulation results show that the algorithm is effective and feasible for path-planning in the AS/RS system Key Words: AGV, path planning. Dijkstra algorithm, shortest path, shortest time 1 INTRODUCTION Storage and Retrieval System (AS/RS) can get access to and store materials automatically without In the AS/RS system, the work environment of AGV is i.e. the place where the human intervention. As the main transportation tool in the freight is put up or put down) and the path connecting the AS/RS system, Automated Guided Vehicle (AGV) takes Work stations. The shelves are usually arranged in the the task of transporting freight from a designated starting regular form of lines and rows. The shape of the work node to a destination node in the given storage environment environment then appears as regular "rectangle". Then Based on an effective path planning, AGV can complete the more than one equidistance shortest path maybe exists comprised of the work stations between any pair of starting and destination nodes. Even if efficiency as well. Therefore, the path planning prolem he AGV moves the same distance, the path with more turn task within the shortest time, save energy and improve has gotten widespread attention for the AGV research. will spend more time. However, the traditional Dijkstra The AGV path planning belongs to the single source algorithm can only find a single shortest path. Furthermore, shortest path problem. The problem is solved via various since the traditional Dijkstra algorithm only considers the algorithms, such as graph theory, dynamic programming method, neural network method, genctic algorithm and maybe doesn't meet the requirement for the shortest travel hybrid algorithm and so on. Using the ant colony time algorithm, Cao and Wang 2] built the network dataerefore, in view of the property of the path-planning structure to find the shortest path, and designed the shortest problem in the AS/RS system, we presented an improved priority path search algorithm based on the node and the arc. Dijkstra algorithm-it saves all equidistant An improved particle swarm optimization algorithm is used during path searching, and chooses the optimal path from to solve the global path planning problem [3)] travel distance but not the travel time, the shortest path several equidistant paths according to the turn time thus The Dijkstra algorithm proposed in 1959 by Edsger the path with both the shortest distance and time is Dijkstra [4] is a well known shortest path algorithm. The obtained Dijkstra algorithm is implemented easily, performed stably ENVIRONMENT MODEL and adapted ably to the topology change. Thus, it has been widely used to solve the AGV path planning problem. The described labeling strategy of Dijkstra algorithm is improved for searching the shortest path in the directed graph [5). In this work, the environment map of the AGV is using topological method. The work stations and moving paths of AGV are regarded as node- are structure and stored in grid data format. It is assumed as follows: An improved A algorithm is proposed based on Dijkstra (The AGV moves in two-dimensional plane and its algorithm [6]. The turning factor is introduced to make AGV path gentler and an edge removal-based A" algorithm is used to solve the shortest path problem. He et al. [7) regarded AGV as a particle without considering its size to movement of AGV is bi-directional when it moves trough make it easier to build model and do simulation in the AS/RS environment. speed is fixed as 0.2m/s (2) The distance between two adjacent work stations is equal, and set as Im. The map is undirected, ie. the any path; (3) AGV can be regarded as a particle The topological map describing the work environment of
