Networked.life.q21 Wikia
Advertisement

Introducing the Dijkstra algorithm in detail. Illustrates the implementation method of the algorithm and the algorithm of disadvantages: the need to put inside network nodes square level.  Detail at the same time an optimization algorithm based on Dijkstra algorithm—adjacency node algorithm. The algorithm makes full use of the network topology information of segmental arc connection relations, avoid using contains a lot of the incidence matrix of infinite value, make it more suitable for a turn to the restrictions of the real data of the shortest path algorithm and a large number of nodes. Practice has proved that the algorithm can save a lot of memory, for network nodes is larger, or with a large number of turn to the restrictions of the network, has good applicability.

A Short Answer:[]

It is known to us China has the biggest population in the word.  It is about 1.3 billion.  Urban traffic become more and more problematic in China.  Following the developing speed up, almost everyone has economic ability to get the private car.  Urban traffic is becoming more and more problematic in China.  Increasing the number of vehicles brings a large problem to traffic.  Especially in the morning and evening traffic jam, our traffic situation is so bad, almost standstill. This well infect our life quality for many urban dwellers.  Then the large number of cars causes the gas emitted from the cars exhausted pips polluted the environment.  It Is bad for residents’ health.

This are the main reasons why we choose the public transportation.

As for the solution, Chinese government spend a lot of energy and money to improving the public transportation. Now the public transportation is well developed.  China also has special roads for bus.

A Long Answer:[]

1.introduction[]

Network analysis is one of very important spatial analysis functions in GIS. The shortest path analysis is the core of the network analysis algorithms. Network analysis of the efficiency of the algorithm determines the function and efficiency. In a large number of the short-circuit algorithm. Dijkstra algorithm is one of the most classic method. Many algorithms are on the basis of the algorithm and is improved.  This article is on the detailed study on the basis of the algorithm. The topology vector data. Meet the demand of practical application of network analysis and optimization of an algorithm. This article first introduced Dijkstra algorithm, and illustrate the defects of the algorithm. And based on this, advances a new method of optimization.

2.shortest path[]

There a many different types of shortest path. The shortest path between two points, the shortest path of all nodes, kth shortest path and so on. The “shortest” has different meanings.  It can refer to the “shortest” as “shortest time” or “shortest distance”. The Shortest Path can be applied to a lot of situations.  There are many algorithms for solving the shortest path.  This research uses the Dijkstra algorithm to calculate the shortest path in China public transportation.  The Dijkstra algorithm is suit for China public transportation. The reason is we know the start point and we can use Dijkstra algorithm to calculate the shortest distance to any other points.

3.Dijksta algorithm[]

Dijkstra algorithm is an algorithm for finding the shortest path between two nodes.  It was discovered by Edsgar W Dijkstra in 1956 a published in 1959.  The Dijkstra algorithm is the solution to the single-source shortest path problem in a graph.  It can be directed and undirected graphs. All edges must have nonnegative weights Graph must be connected. 

3.1Dijksta algorithm theory[]

Assumption D = ( V , A , w ) is a nonnegative power network,  V  = ( v1 , v2 , ⋯,Vn) ,It is the most short circuit long satisfy equation D( vi , vj)  ∈A:

(1).jpg

If D from vertices v1 to the rest of the vertices in the shortest circuit long sorted by size:

(1).0.jpg

i1 = 1, ui1 = 0, by (1) we can get:

(1).1.png

When k > j, Uik is bigger or equals to uij and wikij is bigger or equals 0,thus

(1).2.png

that it

(1).3.jpg

so

(1).4.jpg

It is easy to prove that

(1).5.jpg

The uij is the shortest path from ui to uj in D, j=1,2,···,n. 

3.2 Example[]

In figure 1 shows a simple network, the relationship between nodes according to their distance, formation of adjacency matrix and distance matrix, on this basis, use the method of coloring said Dijkstra calculation method, calculate the shortest distance from point A to point D is as follows:

Step 1:

Set A is colored, d ( A ) = 0 , d (D) = ∞, so y = A

Step 2:

d(B1)=min(d(B1) , d(A)+a(A, B1))=min( ∞,0+4) = 4

d(B 2)=min(d(B2) , d(A)+a(A, B2))=min( ∞ ,0+5) = 5

d(B3)=min(d(B3) , d(A)+a(A, B3))=min( ∞ ,0+3) = 3

d(B3)=3 is the minimum, so color the B3.

D was not coloring, then continue.

Step 3:

Let y = B3

d (B1)= min ( d (B1) , d (B3) + a (B3, B1) = min (4,∞) = 4

d (B2)= min ( d (B2) , d (B3) + a (B3, B2) = min ( 5,3 + 3) = 5

d (C2)= min ( d (C2) , d (B3) + a (B3, C2) = min (∞ ,3 + 3) = 6

d(B1) = 3 as a minimum, the B1 colored.

Now D has not been coloring, continue.

Step 4:

Let y = B1

d (B2)= min ( d (B2) , d (B1) + a (B1, B2) = min (5,4+3) = 5

d (C1)= min ( d (C1) , d (B1) + a (B1, C1) = min (∞,4 + 4) = 8

d(B2) = 5 as a minimum, the B2 colored.

Now D has not been coloring, continue.

Step 5:

Let y = B2

d(C3) = min ( d (C3) , d (B2) + a (C3, B2) = min ( ∞ ,5 + 2) = 7

d(C2)= 6

d(C2)=5 as a minimum, the C2 color.

Now D has not been coloring, continue.

Step 6:

Let y = C2

d ( D) = min ( d ( D) , d ( C2) + a ( C2 , D) ) = min ( ∞ ,6 +5) = 11

d (C3) = min ( d ( C3) , d ( C2)  + a (C2 , C3) )  = min ( 7 ,6+ 2) = 7

D (C3) = 7 for a minimum of C3 coloring.

D has not been coloring, continue.

Step 7:

Set y = C3

d (D) = min (d (D), d (C3) + a (C3, D)) = min (10,6+4) = 10

d (C1) = min (d (C1), d (C3) + a (C1, C3))  = min ( 8 ,7+ 2) = 9

D (C1) = 9 for a minimum of C1.

D has not been coloring, continue to implement.

Step 8:

d (D) = min (d ( D) , d ( C1) + a ( C1 , D)) = min (10 ,9 + 4)= 10

D color, stop counting.

The result is the shortest distance from A to D is 10.

Figure 1.jpg
Matrix.jpg

3.3 The shortcoming of Dijkstra algorithm[]

Using Dijkstra algorithm based on the network weight matrix algorithms and applications in solving the shortest circuit, using the concept of incidence matrix adjacency matrix and distance matrix.  In graphic data storage and computing, the need to define the N number group, where N as the nodes of the network, when the network nodes is bigger, will occupy a large amount of computer memory.  If no Dijkstra algorithm is optimized, the calculate method applied in the actual very hard.

Advertisement