This paper presents a coupled neural network, called output-threshold coupled neural network (OTCNN), which can mimic the autowaves in the present pulsed coupled neural networks (PCNNs), by the construction of mutual ...This paper presents a coupled neural network, called output-threshold coupled neural network (OTCNN), which can mimic the autowaves in the present pulsed coupled neural networks (PCNNs), by the construction of mutual coupling between neuron outputs and the threshold of a neuron. Based on its autowaves, this paper presents a method for finding the shortest path in shortest time with OTCNNs. The method presented here features much fewer neurons needed, simplicity of the structure of the neurons and the networks, and large scale of parallel computation. It is shown that OTCNN is very effective in finding the shortest paths from a single start node to multiple destination nodes for asymmetric weighted graph, with a number of iterations proportional only to the length of the shortest paths, but independent of the complexity of the graph and the total number of existing paths in the graph. Finally, examples for finding the shortest path are presented.展开更多
The All-pairs shortest path problem(ALL-SPP)aims to find the shortest path joining all the vertices in a given graph.This study proposed a new optimal method,Dhouib-matrix-ALL-SPP(DM-ALL-SPP)to solve the ALL-SPP based...The All-pairs shortest path problem(ALL-SPP)aims to find the shortest path joining all the vertices in a given graph.This study proposed a new optimal method,Dhouib-matrix-ALL-SPP(DM-ALL-SPP)to solve the ALL-SPP based on column-row navigation through the adjacency matrix.DM-ALL-SPP is designed to generate in a single execution the shortest path with details among all-pairs of vertices for a graph with positive and negative weighted edges.Even for graphs with a negative cycle,DM-ALL-SPP reported a negative cycle.In addition,DM-ALL-SPP continues to work for directed,undirected and mixed graphs.Furthermore,it is characterized by two phases:the first phase consists of adding by column repeated(n)iterations(where n is the number of vertices),and the second phase resides in adding by row executed in the worst case(n∗log(n))iterations.The first phase,focused on improving the elements of each column by adding their values to each row and modifying them with the smallest value.The second phase is emphasized by rows only for the elements modified in the first phase.Different instances from the literature were used to test the performance of the proposed DM-ALL-SPP method,which was developed using the Python programming language and the results were compared to those obtained by the Floyd-Warshall algorithm.展开更多
The Floyd-Warshall algorithm is frequently used to determine the shortest path between any pair of nodes.It works well for crisp weights,but the problem arises when weights are vague and uncertain.Let us take an examp...The Floyd-Warshall algorithm is frequently used to determine the shortest path between any pair of nodes.It works well for crisp weights,but the problem arises when weights are vague and uncertain.Let us take an example of computer networks,where the chosen path might no longer be appropriate due to rapid changes in network conditions.The optimal path from among all possible courses is chosen in computer networks based on a variety of parameters.In this paper,we design a new variant of the Floyd-Warshall algorithm that identifies an All-Pair Shortest Path(APSP)in an uncertain situation of a network.In the proposed methodology,multiple criteria and theirmutual associationmay involve the selection of any suitable path between any two node points,and the values of these criteria may change due to an uncertain environment.We use trapezoidal picture fuzzy addition,score,and accuracy functions to find APSP.We compute the time complexity of this algorithm and contrast it with the traditional Floyd-Warshall algorithm and fuzzy Floyd-Warshall algorithm.展开更多
文摘This paper presents a coupled neural network, called output-threshold coupled neural network (OTCNN), which can mimic the autowaves in the present pulsed coupled neural networks (PCNNs), by the construction of mutual coupling between neuron outputs and the threshold of a neuron. Based on its autowaves, this paper presents a method for finding the shortest path in shortest time with OTCNNs. The method presented here features much fewer neurons needed, simplicity of the structure of the neurons and the networks, and large scale of parallel computation. It is shown that OTCNN is very effective in finding the shortest paths from a single start node to multiple destination nodes for asymmetric weighted graph, with a number of iterations proportional only to the length of the shortest paths, but independent of the complexity of the graph and the total number of existing paths in the graph. Finally, examples for finding the shortest path are presented.
文摘The All-pairs shortest path problem(ALL-SPP)aims to find the shortest path joining all the vertices in a given graph.This study proposed a new optimal method,Dhouib-matrix-ALL-SPP(DM-ALL-SPP)to solve the ALL-SPP based on column-row navigation through the adjacency matrix.DM-ALL-SPP is designed to generate in a single execution the shortest path with details among all-pairs of vertices for a graph with positive and negative weighted edges.Even for graphs with a negative cycle,DM-ALL-SPP reported a negative cycle.In addition,DM-ALL-SPP continues to work for directed,undirected and mixed graphs.Furthermore,it is characterized by two phases:the first phase consists of adding by column repeated(n)iterations(where n is the number of vertices),and the second phase resides in adding by row executed in the worst case(n∗log(n))iterations.The first phase,focused on improving the elements of each column by adding their values to each row and modifying them with the smallest value.The second phase is emphasized by rows only for the elements modified in the first phase.Different instances from the literature were used to test the performance of the proposed DM-ALL-SPP method,which was developed using the Python programming language and the results were compared to those obtained by the Floyd-Warshall algorithm.
基金extend their appreciation to the Deanship of Scientific Research at King Khalid University for funding this work through General Research Project under Grant No.(R.G.P.2/48/43).
文摘The Floyd-Warshall algorithm is frequently used to determine the shortest path between any pair of nodes.It works well for crisp weights,but the problem arises when weights are vague and uncertain.Let us take an example of computer networks,where the chosen path might no longer be appropriate due to rapid changes in network conditions.The optimal path from among all possible courses is chosen in computer networks based on a variety of parameters.In this paper,we design a new variant of the Floyd-Warshall algorithm that identifies an All-Pair Shortest Path(APSP)in an uncertain situation of a network.In the proposed methodology,multiple criteria and theirmutual associationmay involve the selection of any suitable path between any two node points,and the values of these criteria may change due to an uncertain environment.We use trapezoidal picture fuzzy addition,score,and accuracy functions to find APSP.We compute the time complexity of this algorithm and contrast it with the traditional Floyd-Warshall algorithm and fuzzy Floyd-Warshall algorithm.
