# Solution to Shortest Path Problem Using a Connective Probe Machine

Authors: Jiuyun Sun; Huanhe Dong; Yuan Kong; Yong Fang
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

With the continuous urban scale expansion, traffic networks have become extremely complex. Finding an optimal route in the shortest time has become a difficult and important issue in traffic engineering study. In this study, a novel computing model, namely, probe machine, is used to solve this problem. Similar to previous studies, urban transport networks can be abstracted into maps, in which points representing places of origin, destinations, and other buildings constitute the data library and edges representing the road make up the probe library. The true solution can be obtained after one probe operation on the computing platform. And by comparing the solving process with Dijkstra’s and Floyd’s algorithms, the computing efficiency of the probe machine is clearly superior, although all three methods can solve the shortest path problem and obtain the same solution.


---

## Body

## 1. Introduction

Traffic engineering is the basic theory of the research and development of traffic engineering discipline. Its main purpose is to seek the transportation system planning, construction and management scheme with the largest travel efficiency, the least traffic accidents, the fastest traffic speed, the least transportation cost, and the lowest energy consumption. The rapid development of urban traffic and increase in the number of vehicles has made travelling more convenient for people in recent years. However, urban traffic is not smooth due to the numerous traffic network nodes and complex sections; some cities suffer from traffic congestion [1, 2]. Finding a suitable path for drivers is not only one of the solutions to promote the development of urban transportation [3–5], but also one of the main purposes in traffic engineering research. Therefore, we must address this issue by determining the shortest path. In traffic engineering, “shortest path” does not necessarily mean the shortest distance, but also the shortest time or the lowest cost.The shortest path problem is a classical problem in graph theory, which has been applied in many fields [6]. Finding the path with the shortest distance is the most basic application of the shortest path problem, which is also a very practical problem. The basic objective of the shortest path problem is to find the path, with the lowest weight, between two points where every edge in the graph has its own weight value. Many algorithms to solve the shortest path problem have been proposed in previous studies, such as Dijkstra’s algorithm [7], Bellman–Ford algorithm [8], and Floyd’s algorithm [9]. The most classical algorithm for solving such a problem is Dijkstra’s algorithm. It can solve the shortest path problem from a given point to any point; however, it fails to solve the shortest path problem with a negative weight. Therefore, Floyd’s algorithm and other algorithms were proposed to solve the above problem.In 2016, Xu proposed a new computing model, i.e., the probe machine [10]. Probe machine is a completely parallel computing model that can simultaneously process multiple pairs of data. Parallel computing can speed up operations, expand the scale of processing problems, and facilitate the ability of algorithms to handle problems [11, 12]. Compared with turing machines, probe machines can solve NP-complete problems after a probe operation, such as the Hamiltonian cycle problem [10], vertex problem [10], travelling salesman problem [13], working operation problem [14], and so on. The probes of a probe machine can be divided into connective probes and transitive probes. A connective probe can connect data fibers from different data, while a transitive probe can transmit information between data fibers from different data. The probe machine is a form of bionic computing. It achieves complete parallelism by imitating the process of information transmission of neurons and reduces computation complexity. Bionic computing refers to the use of biological models to deal with practical problems, and it can often yield unexpected results in some fields [15, 16]. In recent studies, more computational models are used to solve all kinds of NP problems, such as SAT problem [17–21], vehicle routing problem [22–24], graph coloring problem [10, 25, 26], partner selection problem [27], and the other problems [28–33].In this study, we first introduce a probe machine. Then, a shortest path problem, which is a problem of finding the path with the minimum distance, is solved by using Dijkstra’s algorithm, Floyd’s algorithm, and probe machine; the process using the three methods is then compared.


## 2. Probe Machine

The probe machine was first proposed by Professor Xu in 2016. It consists of nine parts including data library (X), probe library (Y), data controller (σ1), probe controller (σ2), probe operation (τ), computing platform (λ), detector (η), true solution storage (Q), and residue collector (C).The data placement mode of the data library is nonlinear. The data library is divided inton data pools X1,X2,…,Xn. Data pool Xi includes one type of data xi, and data xi comprises a body and pi data fibers, as shown in Figure 1.Figure 1
Data library [10].
(a)
(b)
(c)
(d)There are two types of probes in a probe machine, namely, connective probe and transitive probe. A connective probe can connect different data fibers from different data, and a transitive probe can transfer information from the source fiber to a destination fiber. In this study, the connective probe is used to solve the shortest path problem. The set of all probes between two data pools constitutes the probe pool; the probe library is a set of all probe pools, as shown in Figure2. The data controller and probe controller add the corresponding data and probes into the computing platform, respectively. After the probe operation, the resulting aggregation is detected by a detector. The resulting true solution is put into the true solution storage. The residue is put into the residue collection, which decomposes it into basic data and returns it to the data pool, as shown in Figure 2.Figure 2
Connective probe machine [10].


## 3. Solving the Shortest Path Problem

In this study, an example of a directed graph is considered, as shown in Figure3. The points on the graph are represented by v1,v2,v3,v4,v5,v6,v7,v8,v9; the distance from vi to vj is represented by vij. The shortest path from v1 to v8 is obtained. We will use Dijkstra’s algorithm, Floyd’s algorithm, and probe machine to solve the shortest path problem.Figure 3
Shortest path problem.


### 3.1. Solving the Shortest Path Problem Using Dijkstra’s Algorithm

P represents the distance from the starting point to point vi, and T refers to the previous point in the shortest path. Si represents the set of points that have p mark in step i.(1)
i=0, S0=v1, Pv1=0, λv1=0, Tvi=+∞, λvi=M, (i=2,3,…,9)Becausev2∉S0, Pv1+w12<Tv2, let Tv2=Pv1+w12=6, λv2=1;Similarly,Tv3=Pv1+w13=3, λv3=1;Tv4=Pv1+w14=1, λv4=1.Tv4=minTv2,Tv3,Tv4,so, letPv4=1, S1=v1,v4, k=4.(2)
i=1, let Tv6=Pv6+w46=11, λv6=4;Tv3=minTv2,Tv3,Tv6,so, letPv3=3, S2=v1,v4,v3, k=3.(3)
i=2, let Tv6=Pv6+w46=11, λv2=3;Tv2=minTv2,Tv6,so, letPv2=5, S3=v1,v4,v3,v2, k=2.(4)
i=3, let Tv5=Pv2+w25=6, λv5=2;Tv5=minTv5,Tv6,so, letPv5=6, S4=v1,v4,v3,v2,v5, k=5.(5)
i=4, let Tv6=Pv5+w56=10, λv6=5,Tv7=Pv7+w57=9, λv7=5,Tv8=Pv5+w58=12, λv8=5,Tv9=Pv5+w59=8, λv9=5,Tv9=minTv6,Tv7,Tv8,Tv9,so, letPv9=8, S5=v1,v4,v3,v2,v5,v9, k=9.(6)
i=5, let Tv8=Pv9+w98=12, λv8=5;Tv7=minTv6,Tv7,Tv8,so, letPv7=9, S6=v1,v4,v3,v2,v5,v9,v7, k=7.(7)
i=6, Tv6=minTv6,Tv8,so, letPv6=9, S7=v1,v4,v3,v2,v5,v9,v7,v6, k=6.(8)
i=7, let Pv8=11, S8=v1,v4,v3,v2,v5,v9,v7,v6,v8, k=8.So, the shortest path fromv1 to v8 is v1⟶v3⟶v2⟶v5⟶v9⟶v8, as shown in Figure 4.Figure 4
The shortest path.


### 3.2. Solving the Shortest Path Problem Using Floyd’s Algorithm

According to the graph, the adjacency matrix of the graph is as follows:(1)A=0631∞∞∞∞∞∞0∞∞1∞∞∞∞∞202∞∞∞∞∞∞∞∞0∞10∞∞∞∞∞∞604362∞∞∞∞∞02∞∞∞∞∞∞∞∞04∞∞∞∞∞∞∞∞0∞∞∞∞∞∞∞∞30.Step 1: takingv2 as the intermediary point and updating the matrix,(2)A=06317∞∞∞∞∞0∞∞1∞∞∞∞∞2023∞∞∞∞∞∞∞0∞10∞∞∞∞∞∞604362∞∞∞∞∞02∞∞∞∞∞∞∞∞04∞∞∞∞∞∞∞∞0∞∞∞∞∞∞∞∞30.Step 2: takingv3 as the intermediary point and updating the matrix,(3)A=05317∞∞∞∞∞0∞∞1∞∞∞∞∞2023∞∞∞∞∞∞∞0∞10∞∞∞∞∞∞604362∞∞∞∞∞02∞∞∞∞∞∞∞∞04∞∞∞∞∞∞∞∞0∞∞∞∞∞∞∞∞30.Step 3: takingv4 as the intermediary point and updating the matrix,(4)A=0531711∞∞∞∞0∞∞1∞∞∞∞∞202312∞∞∞∞∞∞0∞10∞∞∞∞∞∞604362∞∞∞∞∞02∞∞∞∞∞∞∞∞04∞∞∞∞∞∞∞∞0∞∞∞∞∞∞∞∞30.Step 4: takingv5 as the intermediary point and updating the matrix,(5)A=053171110139∞0∞715473∞20237695∞∞∞0∞10∞∞∞∞∞∞604362∞∞∞∞∞02∞∞∞∞∞∞∞∞04∞∞∞∞∞∞∞∞0∞∞∞∞∞∞∞∞30.Step 5: takingv6 as the intermediary point and updating the matrix,(6)A=053171110139∞0∞715473∞20237695∞∞∞0∞1012∞∞∞∞∞604362∞∞∞∞∞02∞∞∞∞∞∞∞∞04∞∞∞∞∞∞∞∞0∞∞∞∞∞∞∞∞30.Step 6: takingv7 as the intermediary point and updating the matrix,(7)A=053171110139∞0∞715473∞20237695∞∞∞0∞101216∞∞∞∞604362∞∞∞∞∞026∞∞∞∞∞∞∞04∞∞∞∞∞∞∞∞0∞∞∞∞∞∞∞∞30.Step 7: takingv9 as the intermediary point and updating the matrix,(8)A=053171110129∞0∞715463∞20237685∞∞∞0∞101216∞∞∞∞604352∞∞∞∞∞026∞∞∞∞∞∞∞04∞∞∞∞∞∞∞∞0∞∞∞∞∞∞∞∞30.Thus, the shortest path fromv1 to v8 is v1⟶v3⟶v2⟶v5⟶v9⟶v8.


### 3.3. Solving the Shortest Path Problem Using the Probe Machine

The probe machine solves the shortest path problem as follows.


#### 3.3.1. Data Library Construction

(9)
X
=
∪
i
=
1
9
E
2
v
i
.
E
2
v
i is the data pool of vi, and E2vi is a set of two long paths centered around vi. The two long paths are denoted as vilj, and i,l,j are different from each other. At the same time, because this problem is a directed graph, each path has one data fiber. The data library is as follows:(10)X=∪i=19E2vi,E2v1=∅,E2v2=x215,x235,E2v3=x312,x314,E2v4=x416,x436,x456,E2v5=x524,x526,x527,x528,x529,E2v6=x647,x657,E2v7=x768,x758,E2v8=∅,E2v9=x958.The data fibers are as follows:(11)ℑx215=x2155,ℑx235=x2354,ℑx312=x3122,ℑx314=x3144,ℑx416=x4166,ℑx436=x4366,ℑx456=x4566,ℑx524=x5244,ℑx526=x5266,ℑx527=x5277,ℑx528=x5288,ℑx529=x5299,ℑx647=x6477,ℑx657=x6577,ℑx768=x7688,ℑx758=x7588,ℑx958=x9588.


#### 3.3.2. Probe Library Construction

In order to avoid arbitrary data aggregation, if there is a probe between datavilj and vtab, one of the following two conditions need to be met:(12)1i,l,j∩t,a,b=l,j∩a,b=1,2t∈l,j,i∈a,b,l,j∩a,b=0.At the same time, without loss of generality, because this is a directed graph, the direction of the probe needs to be same as the direction of the edge. The probe library established is as follows:(13)Y=∪i=1,t=2i=8,t=9Yit,i<t,Y23=x2355x3122¯,Y24=x2155x4566¯,x2355x4566¯,Y25=x2155x5244¯,x2155x5266¯,x2155x5277¯,x2155x5288¯,x2155x5299¯,x2355x5244¯,x2355x5266¯,x2355x5277¯,x2355x5288¯,x2355x5299¯,Y26=x2155x6577¯,x2355x6577¯,Y27=x2155x7588¯,x2355x7588¯,Y29=x2155x9588¯,x2355x9588¯,Y34=x3144x4366¯,Y35=x3122x5244¯,x3122x5266¯,x3122x5277¯,x3122x5288¯,x3122x5299¯,Y36=x3144x6577¯,Y45=x4566x5244¯,Y46=x4166x6477¯,x4366x6477¯,x4566x6477¯,Y47=x4166x7688¯,x4366x7688¯,x4566x7688¯,Y56=x5244x6477¯,x5266x6577¯,Y57=x5266x7688¯,x5277x7588¯,Y59=x5299x9588¯,Y67=x6477x7688¯,x6577x7688¯.


#### 3.3.3. Probe Operation

The data controller and probe controller are used to extract the corresponding amount of data and probes from the data library and probe library and add them to the computing platform. After the probe operation, all possible solutions to the problem are obtained. Through the detector, the optimal solution is output as follows:(14)v1⟶v3⟶v2⟶v5⟶v9⟶v8.


## 3.1. Solving the Shortest Path Problem Using Dijkstra’s Algorithm

P represents the distance from the starting point to point vi, and T refers to the previous point in the shortest path. Si represents the set of points that have p mark in step i.(1)
i=0, S0=v1, Pv1=0, λv1=0, Tvi=+∞, λvi=M, (i=2,3,…,9)Becausev2∉S0, Pv1+w12<Tv2, let Tv2=Pv1+w12=6, λv2=1;Similarly,Tv3=Pv1+w13=3, λv3=1;Tv4=Pv1+w14=1, λv4=1.Tv4=minTv2,Tv3,Tv4,so, letPv4=1, S1=v1,v4, k=4.(2)
i=1, let Tv6=Pv6+w46=11, λv6=4;Tv3=minTv2,Tv3,Tv6,so, letPv3=3, S2=v1,v4,v3, k=3.(3)
i=2, let Tv6=Pv6+w46=11, λv2=3;Tv2=minTv2,Tv6,so, letPv2=5, S3=v1,v4,v3,v2, k=2.(4)
i=3, let Tv5=Pv2+w25=6, λv5=2;Tv5=minTv5,Tv6,so, letPv5=6, S4=v1,v4,v3,v2,v5, k=5.(5)
i=4, let Tv6=Pv5+w56=10, λv6=5,Tv7=Pv7+w57=9, λv7=5,Tv8=Pv5+w58=12, λv8=5,Tv9=Pv5+w59=8, λv9=5,Tv9=minTv6,Tv7,Tv8,Tv9,so, letPv9=8, S5=v1,v4,v3,v2,v5,v9, k=9.(6)
i=5, let Tv8=Pv9+w98=12, λv8=5;Tv7=minTv6,Tv7,Tv8,so, letPv7=9, S6=v1,v4,v3,v2,v5,v9,v7, k=7.(7)
i=6, Tv6=minTv6,Tv8,so, letPv6=9, S7=v1,v4,v3,v2,v5,v9,v7,v6, k=6.(8)
i=7, let Pv8=11, S8=v1,v4,v3,v2,v5,v9,v7,v6,v8, k=8.So, the shortest path fromv1 to v8 is v1⟶v3⟶v2⟶v5⟶v9⟶v8, as shown in Figure 4.Figure 4
The shortest path.


## 3.2. Solving the Shortest Path Problem Using Floyd’s Algorithm

According to the graph, the adjacency matrix of the graph is as follows:(1)A=0631∞∞∞∞∞∞0∞∞1∞∞∞∞∞202∞∞∞∞∞∞∞∞0∞10∞∞∞∞∞∞604362∞∞∞∞∞02∞∞∞∞∞∞∞∞04∞∞∞∞∞∞∞∞0∞∞∞∞∞∞∞∞30.Step 1: takingv2 as the intermediary point and updating the matrix,(2)A=06317∞∞∞∞∞0∞∞1∞∞∞∞∞2023∞∞∞∞∞∞∞0∞10∞∞∞∞∞∞604362∞∞∞∞∞02∞∞∞∞∞∞∞∞04∞∞∞∞∞∞∞∞0∞∞∞∞∞∞∞∞30.Step 2: takingv3 as the intermediary point and updating the matrix,(3)A=05317∞∞∞∞∞0∞∞1∞∞∞∞∞2023∞∞∞∞∞∞∞0∞10∞∞∞∞∞∞604362∞∞∞∞∞02∞∞∞∞∞∞∞∞04∞∞∞∞∞∞∞∞0∞∞∞∞∞∞∞∞30.Step 3: takingv4 as the intermediary point and updating the matrix,(4)A=0531711∞∞∞∞0∞∞1∞∞∞∞∞202312∞∞∞∞∞∞0∞10∞∞∞∞∞∞604362∞∞∞∞∞02∞∞∞∞∞∞∞∞04∞∞∞∞∞∞∞∞0∞∞∞∞∞∞∞∞30.Step 4: takingv5 as the intermediary point and updating the matrix,(5)A=053171110139∞0∞715473∞20237695∞∞∞0∞10∞∞∞∞∞∞604362∞∞∞∞∞02∞∞∞∞∞∞∞∞04∞∞∞∞∞∞∞∞0∞∞∞∞∞∞∞∞30.Step 5: takingv6 as the intermediary point and updating the matrix,(6)A=053171110139∞0∞715473∞20237695∞∞∞0∞1012∞∞∞∞∞604362∞∞∞∞∞02∞∞∞∞∞∞∞∞04∞∞∞∞∞∞∞∞0∞∞∞∞∞∞∞∞30.Step 6: takingv7 as the intermediary point and updating the matrix,(7)A=053171110139∞0∞715473∞20237695∞∞∞0∞101216∞∞∞∞604362∞∞∞∞∞026∞∞∞∞∞∞∞04∞∞∞∞∞∞∞∞0∞∞∞∞∞∞∞∞30.Step 7: takingv9 as the intermediary point and updating the matrix,(8)A=053171110129∞0∞715463∞20237685∞∞∞0∞101216∞∞∞∞604352∞∞∞∞∞026∞∞∞∞∞∞∞04∞∞∞∞∞∞∞∞0∞∞∞∞∞∞∞∞30.Thus, the shortest path fromv1 to v8 is v1⟶v3⟶v2⟶v5⟶v9⟶v8.


## 3.3. Solving the Shortest Path Problem Using the Probe Machine

The probe machine solves the shortest path problem as follows.


### 3.3.1. Data Library Construction

(9)
X
=
∪
i
=
1
9
E
2
v
i
.
E
2
v
i is the data pool of vi, and E2vi is a set of two long paths centered around vi. The two long paths are denoted as vilj, and i,l,j are different from each other. At the same time, because this problem is a directed graph, each path has one data fiber. The data library is as follows:(10)X=∪i=19E2vi,E2v1=∅,E2v2=x215,x235,E2v3=x312,x314,E2v4=x416,x436,x456,E2v5=x524,x526,x527,x528,x529,E2v6=x647,x657,E2v7=x768,x758,E2v8=∅,E2v9=x958.The data fibers are as follows:(11)ℑx215=x2155,ℑx235=x2354,ℑx312=x3122,ℑx314=x3144,ℑx416=x4166,ℑx436=x4366,ℑx456=x4566,ℑx524=x5244,ℑx526=x5266,ℑx527=x5277,ℑx528=x5288,ℑx529=x5299,ℑx647=x6477,ℑx657=x6577,ℑx768=x7688,ℑx758=x7588,ℑx958=x9588.


### 3.3.2. Probe Library Construction

In order to avoid arbitrary data aggregation, if there is a probe between datavilj and vtab, one of the following two conditions need to be met:(12)1i,l,j∩t,a,b=l,j∩a,b=1,2t∈l,j,i∈a,b,l,j∩a,b=0.At the same time, without loss of generality, because this is a directed graph, the direction of the probe needs to be same as the direction of the edge. The probe library established is as follows:(13)Y=∪i=1,t=2i=8,t=9Yit,i<t,Y23=x2355x3122¯,Y24=x2155x4566¯,x2355x4566¯,Y25=x2155x5244¯,x2155x5266¯,x2155x5277¯,x2155x5288¯,x2155x5299¯,x2355x5244¯,x2355x5266¯,x2355x5277¯,x2355x5288¯,x2355x5299¯,Y26=x2155x6577¯,x2355x6577¯,Y27=x2155x7588¯,x2355x7588¯,Y29=x2155x9588¯,x2355x9588¯,Y34=x3144x4366¯,Y35=x3122x5244¯,x3122x5266¯,x3122x5277¯,x3122x5288¯,x3122x5299¯,Y36=x3144x6577¯,Y45=x4566x5244¯,Y46=x4166x6477¯,x4366x6477¯,x4566x6477¯,Y47=x4166x7688¯,x4366x7688¯,x4566x7688¯,Y56=x5244x6477¯,x5266x6577¯,Y57=x5266x7688¯,x5277x7588¯,Y59=x5299x9588¯,Y67=x6477x7688¯,x6577x7688¯.


### 3.3.3. Probe Operation

The data controller and probe controller are used to extract the corresponding amount of data and probes from the data library and probe library and add them to the computing platform. After the probe operation, all possible solutions to the problem are obtained. Through the detector, the optimal solution is output as follows:(14)v1⟶v3⟶v2⟶v5⟶v9⟶v8.


## 3.3.1. Data Library Construction

(9)
X
=
∪
i
=
1
9
E
2
v
i
.
E
2
v
i is the data pool of vi, and E2vi is a set of two long paths centered around vi. The two long paths are denoted as vilj, and i,l,j are different from each other. At the same time, because this problem is a directed graph, each path has one data fiber. The data library is as follows:(10)X=∪i=19E2vi,E2v1=∅,E2v2=x215,x235,E2v3=x312,x314,E2v4=x416,x436,x456,E2v5=x524,x526,x527,x528,x529,E2v6=x647,x657,E2v7=x768,x758,E2v8=∅,E2v9=x958.The data fibers are as follows:(11)ℑx215=x2155,ℑx235=x2354,ℑx312=x3122,ℑx314=x3144,ℑx416=x4166,ℑx436=x4366,ℑx456=x4566,ℑx524=x5244,ℑx526=x5266,ℑx527=x5277,ℑx528=x5288,ℑx529=x5299,ℑx647=x6477,ℑx657=x6577,ℑx768=x7688,ℑx758=x7588,ℑx958=x9588.


## 3.3.2. Probe Library Construction

In order to avoid arbitrary data aggregation, if there is a probe between datavilj and vtab, one of the following two conditions need to be met:(12)1i,l,j∩t,a,b=l,j∩a,b=1,2t∈l,j,i∈a,b,l,j∩a,b=0.At the same time, without loss of generality, because this is a directed graph, the direction of the probe needs to be same as the direction of the edge. The probe library established is as follows:(13)Y=∪i=1,t=2i=8,t=9Yit,i<t,Y23=x2355x3122¯,Y24=x2155x4566¯,x2355x4566¯,Y25=x2155x5244¯,x2155x5266¯,x2155x5277¯,x2155x5288¯,x2155x5299¯,x2355x5244¯,x2355x5266¯,x2355x5277¯,x2355x5288¯,x2355x5299¯,Y26=x2155x6577¯,x2355x6577¯,Y27=x2155x7588¯,x2355x7588¯,Y29=x2155x9588¯,x2355x9588¯,Y34=x3144x4366¯,Y35=x3122x5244¯,x3122x5266¯,x3122x5277¯,x3122x5288¯,x3122x5299¯,Y36=x3144x6577¯,Y45=x4566x5244¯,Y46=x4166x6477¯,x4366x6477¯,x4566x6477¯,Y47=x4166x7688¯,x4366x7688¯,x4566x7688¯,Y56=x5244x6477¯,x5266x6577¯,Y57=x5266x7688¯,x5277x7588¯,Y59=x5299x9588¯,Y67=x6477x7688¯,x6577x7688¯.


## 3.3.3. Probe Operation

The data controller and probe controller are used to extract the corresponding amount of data and probes from the data library and probe library and add them to the computing platform. After the probe operation, all possible solutions to the problem are obtained. Through the detector, the optimal solution is output as follows:(14)v1⟶v3⟶v2⟶v5⟶v9⟶v8.


## 4. Results and Discussion

Although all three methods can solve the shortest path problem and obtain the same solution, there are some obvious differences in the solving process and computing efficiency. Dijkstra’s algorithm is based on the breadth-first search algorithm, which calculates the shortest path from the starting point to all other points. The calculation step of Dijkstra’s algorithm is to expand from the starting point to the layer by layer. Floyd’s algorithm is based on dynamic programming algorithm to find the shortest path between any two points in the graph. The first step of Floyd’s algorithm is to find the adjacency matrix of the graph, and the second step is to update the adjacency matrix by taking each point as the intermediate point. And, the solution process of the probe machine is mainly divided into two steps: the first step is to build the data library and the probe library, and the second step is to get all possible solutions through the probe operation. It can be seen from the solution process that each step of Dijkstra’s algorithm and the Floyd algorithm is part of solving the shortest path problem, but the real solution process of the probe machine is only probe operation. The purpose of the remaining steps of the probe machine is to prepare for the probe operation or to screen the solution calculated by the probe operation. This phenomenon should be attributed to the way of storing data. When the Dijkstra algorithm and the Floyd algorithm are used, the linear data placement mode and the sequential data processing mode are taken, so the solution process needs to be performed step by step; however, in the probe machine, a nonlinear data storage method is adopted, so the probe machine can simultaneously process multiple pairs of data. In other words, the probe machine is a completely parallel computational model, which is the biggest difference between the probe machine and other computing models.Moreover, Dijkstra’s and Floyd’s algorithms are only used to deal with problems in graph theory. The probe machine is a completely parallel computing model, which can also get the true solution after one probe operation when solving NP-complete problems. Although we only use the probe machine to deal with the shortest path problem in this paper, we can see the powerful computing power of the probe machine through the solving process.


## 5. Conclusion

In urban traffic planning, the shortest path problem is a very basic problem. In this study, a probe machine was used to solve this problem. It can solve complex traffic problems after a single probe operation, which improves the efficiency and shortens the time required for solving traffic planning problems. When dealing with actual traffic problems, the speed at which a probe machine solves them is much higher than the speed of other models. A probe machine has high computing power; however, it is still a new concept. It has several shortcomings and needs to be improved further to handle specific problems. For example, when dealing with complex traffic problems, complex data and probe libraries need to be constructed. The process of constructing these libraries cannot be completely replaced by a probe machine or computer. The more complex the problem to be solved is, the more difficult it becomes to construct data library and probe library. In the future, we will continue to study the probe machine and attempt to improve it.



---

*Source: 8709042-2019-11-07.xml*