2021-09-22T11:17:55Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000600832017-03-31T05:37:45Z05550:05552
An Algorithm for Generating All The Directed Paths and Its ApplicationAn Algorithm for Generating All The Directed Paths and Its Applicationenghttp://id.nii.ac.jp/1001/00060083/Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=60083&item_no=1&attribute_id=1&file_no=1Copyright (c) 1976 by the Information Processing Society of JapanDepartment of Electronic Engineering Faculty of Engineering University of OsakaDepartment of Electronic Engineering Faculty of Engineering University of OsakaDepartment of Electronic Engineering Faculty of Engineering University of OsakaDepartment of Electronic Engineering Faculty of Engineering University of OsakaAmTranDinhShuji, TsukiyamaIsao, ShirakawaHiroshi, OzakiAn algorithm to generate all the directed paths from a specified vertex to an-other one in a given graph is proposed. The algorithm requires the processing tine bounded by the order O( (n+m) (p+1) ) and memory space bounded by O(n+m) where n m and p denote the numbers of vertices edges and directed paths in a given graph respectively. As an application of the algorithm the shortest or longest path problem in a directed graph containing cycles of negative weight is also considered.An algorithm to generate all the directed paths from a specified vertex to an-other one in a given graph is proposed. The algorithm requires the processing tine bounded by the order O( (n+m) (p+1) ) and memory space bounded by O(n+m) , where n, m, and p denote the numbers of vertices, edges, and directed paths in a given graph, respectively. As an application of the algorithm, the shortest or longest path problem in a directed graph containing cycles of negative weight is also considered.AA00674393Information Processing in Japan16031351976-01-012009-06-30