tailieunhanh - An algorithm finding the shortest path in an extended weighted graph

An algorithm finding the shortest path joining two given vertices in an extended graph has been studied in other papers. In this paper, we show that the algorithm presented in doesn’t work for the extended graphs in. We define the other extended graph, called an extended weighted graph, such that a similar algorithm works for it. | JOURNAL OF SCIENCE OF HNUE Interdisciplinary Science 2014 Vol. 59 No. 5 pp. 34-41 This paper is available online at http AN ALGORITHM FINDING THE SHORTEST PATH IN AN EXTENDED WEIGHTED GRAPH Pham Thi Hue Xuan Dinh Highschool Tu Liem Distric Hanoi Abstract. An algorithm finding the shortest path joining two given vertices in an extended graph has been studied in other papers 1 6 . In this paper we show that the algorithm presented in 6 doesn t work for the extended graphs in 6 . We define the other extended graph called an extended weighted graph such that a similar algorithm works for it. Keywords Parallel graph extended weighted graph algorithm the shortest path. 1. Introduction In 6 the extended graph is thus defined. Definition 1 Given a graph G V E with a set of vertices V and a set of edges E where the edges can be directed or undirected we denote the weight of an edge e E with wE e . With each vertex v V let Ev be the set of edges of vertex v. For each vertex v V and each edge e e Ev Ev e 6 e weighted wV v e e . The graph G V E wE wV is called an extended graph. Let P u e1 u1 e2 u2 . . . eh uh eh 1 v be the path from u to v through the edge ei i 1 . h 1 and the vertices ui i 1 . h define the length of the path p denoted l p h 1 h 1 X X l p wE ei wV ui ei ei 1 i 1 i 1 The algorithm in 6 is as following - Input. Extended graph G V E we wv vertex s V and set U V . - Output. l v is the length of the shortest path from s to v and the shortest path if l v lt u U. Received April 11 2014. Accepted June 13 2014. Contact Pham Thi Hue e-mail address huecntt@ 34 An algorithm finding the shortest path in an extended weighted graph - Methods. The algorithm uses the following symbols S is a set of vertices that found the shortest path starting from s T V - S l v is the length of the shortest path from s to v VE v e v V s amp e EV s φ is the set of vertices and edges SE is a set of vertex-edge excluded from VE TE VE - SE L v e is the vertex-edge .