The mysterious city of Mohenjo Daro

Read More

Dijkstra’s Algorithm

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edger W. Dijkstra in 1956

The algorithm exists in many variants; Dijkstra's original variant found the shortest path between two nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.

For a, given source node in the graph, the algorithm finds the shortest path between that node and every other. It can also be used for finding the shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined. For example, if the nodes of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between one city and all other cities. As a result, the shortest path algorithm is widely used in network routing protocols, most notably IS-IS and Open Shortest Path First (OSPF). It is also employed as a subroutine in other algorithms such as Johnson's.

Dijkstra’s algorithm is one of the most useful graph algorithms. Dijkstra’s algorithm is one of the most useful graph algorithms.

Algorithm: ShortestPath(G, v)  // a little miss leading since the output is only the distance

input: A simple undirected weighted graph G

with non negative edge weights and a start vertex, v.

output: D(u) the distance u is from v.

Initialize D(v) = 0 and D(u) = ∞ for u != v 

Initialize priority queue Q of vertices using D as key. 

while Q is not empty do

u = Q.removeMin() 
for each vertex z adjacent to u and in Q do

if  D(u) + w((u, z)) < D(z) then

    D(z) = D(u) + w((u, z))

    update z in Q

return D

Dijkstra’s uses:

        Weighted graph

        Distance function or array

        Priority Queue

        Relaxation

The cost is:

O((n+m) lg n) using a heap

O(n² + m) using an unsorted sequence.

Dijkstra's Shortest Path Algorithm and Its Application The shortest path problem exists in variety of areas. A well-known shortest path algorithm is Dijkstra's, also called "label algorithm". Experiment results have shown that the "label algorithm" has the following issue Its exiting mechanism is effective to undirected graph but ineffective to digraph, or even gets into an infinite loop. It hasn't addressed the problem of adjacent vertices in shortest path. It hasn't considered the possibility that many vertices may obtain the "p-label" simultaneously. By addressing these issues, we have improved the algorithm significantly. Our experiment results indicate that the three issues have been effectively resolved. The problem is to find the shortest path between starting vertex and terminal vertex (which exist in a graph or network diagram) is widely used in various fields, such as computer network routing algorithm, the robot Pathfinder, route navigation, game design, and so on. The structure of the paper is as follows first I will introduce Dijkstra’s “label algorithm” second I will point out that the algorithm needs to be improved through experiments; thirdly, we propose an improved algorithm and verified the algorithm through experiments. Experimental results show that improved algorithm is more effective than “label algorithm”, and can solve inadequacies of “label algorithm” effectively.

2. Dijkstra's "Label Algorithm" Dijkstra’s “label algorithm” which was proposed in 1959 is one of the best shortest path algorithms.
“Label algorithm” has a very wide range of applications, such as multi-point routing, surveying and mapping science, the shortest path of logistics and transport, the intelligent transportation system the expressway network toll collection, and so on. There are many related research about the shortest path algorithm and Dijkstra’s “label algorithm” The content of Dijkstra’s “label algorithm” Suppose G = <V, E, W> is a n-order simple weighted graph ( wij ≥0). If vertex vi is not adjacent to vertex v j then set wij ＝∞. To calculate the shortest path between vertex v1 and other vertices in graph.

G. Following are related definitions:(1). Suppose r)*( li is the weight of the shortest path from v1 to vi . If vi obtain the label r)*( li then vi obtain the “p-label” li r)*( (permanent label) in step r(r≥0).

(2). Suppose l jr)( is the upper of the shortest path from v1 to v j .If v j obtain l jr)( then v j obtain “tlabel” r)(l j (temporary label) in step

r. (3). Set P r ＝ { v | v has obtained “p-label”} to be ”pass vertex set” in step r.

(4). Set Tr ＝V- P r to be “not pass vertex set” in step r.
Dijkstra's “label algorithm” is the following:Initial: r←0, l1 )*0( ＝0, P 0 ＝{ v1}, T0 ＝V-{ v1},l j )0( ＝ wij (j≠1). ( v1 obtain “p label”, v j obtain “tlabel”) ①. Find next “p-label” vertex. Set r)*( li ＝min{l jr- )1( }(r≥1). vi obtain “p-label” li r)*( . Update the “pass vertex set” and the “not pass vertex set”:Pr＝Pr-1 ∪{ vi }, Tr＝Tr-1 -{ vi }. check Tr: If Tr＝∅ then the algorithm end else jump ②. Update each vertex’s “t-label” in Tr : r)( l j ＝min{l jr- )1( ,li r)*( + wij }. li r)*( is the latest “p-label”. set r←r+1 and jump ①.
Dijkstra’s label algorithm can effectively solve the shortest path problem of simple weighted undigraph. But Dijkstra’s label algorithm is inadequate and need to be improved. The following will analyze each of them and propose the improvement.
2.2. The Exit Mechanism of Dijkstra's Label Algorithm
The exit mechanism of Dijkstra’s label algorithm is: check Tr (“not pass vertex set” in step r, r≥0), if Tr＝∅ then the algorithm end.
Such an exit mechanism is effective to undigraph but ineffective to digraph. For example, if two vertices are disconnected in a digraph, the system will not shut down and fall into an infinite loop according to the algorithm.

To solve the problem, this paper propose the following exit mechanism: check Tr ( ”not pass vertex set” in step r, r≥0), If Tr ＝∅ then the algorithm end; calculate “p-label” li r)*( ＝min{ l jr- )1( }(r≥1), if r)*(li ＝∞ then the algorithm end.

The adjacent vertices in the shortest path Dijkstra’s label algorithm did not specify how to get adjacent vertices (specific to the previous vertices) in the shortest path. While in practice, it is often needed to find the adjacent vertices in the shortest path. So Dijkstra’s label algorithm needs to be improved. This paper proposes the following improvements: while updating the “t-label” of each vertex in Tr ( v j ) according to vi , if v j ’s “t-label” is updated then vi is the adjacent vertex of v j in the shortest path. Each vertex v j may has more than one adjacent vertices. More than one vertices obtain the p-label simultaneously
Dijkstra’s label algorithm ignores the problem that many vertices may obtain the “p-label” simultaneously. Thus Dijkstra’s label algorithm should be improved.

This paper proposes the following improvements: set li r)*( ＝ min{l jr- )1( }(r≥1) and vi obtain the “plabel” r)*(li . Update Pr and Tr : P r ＝ Pr-1 ∪{ vi }, Tr ＝Tr-1 -{ vi }. If many vertices have the same “tlabel” then these vertices obtain the “p-label” simultaneously.

3. The improved Dijkstra’s label algorithm According to the inadequate of Dijkstra’s label algorithm and the corresponding improvement, this paper proposes an improved algorithm of Dijkstra’s label algorithm Basic definitions.

(1). Suppose li r)*( is the weight of the shortest path between v1 and vi . If vi obtain the label li r)*(then vi obtain the “p-label” li r)*( (permanent label) in step r (r≥0).

(2). Suppose l jr)( is the upper of the shortest path from v1 to v j .If v j obtain l jr)( then v j obtain “tlabel” r)(l j (temporary label) in step r.
(3). Set P r ＝ { v | v has obtained ”p-label”} to be “pass vertex set” in step r.

(4). Set Tr ＝V- P r to be “not pass vertex set” in step r.
(5). Set Ai to be “ vi ’s adjacent vertices set”.

(6).Set Nr to be “vertices which obtain p-label” in step r. Improved algorithm.

The following is the improved algorithm:

Initial: r←0, v1 obtain “p-label”: l1 )*0( ＝0, P 0 ＝ { v1}, T0＝V-{ v1}, v j ’s “t-label” : l j )0( ＝ w1 j , if)0(l j ≠∞ then Aj ＝{ v1} else Aj ＝∅ (j≠1).

①. Find next “p-label” vertex. set min l r- )1( ＝1min-∈Tv rj {l jr- )1( }， r≥1. Nr ＝∅. if min l r- )1( ＝∞ then the algorithm end. check
vi ∈Tr-1 : if li r- )1( ＝ min l r- )1( then vi obtain the “p-label“:li r)*( ＝ min l r- )1( update: P r ＝ Pr-1 ∪{ vi }, Tr ＝Tr-1 -{ vi }, Nr ＝ Nr ∪{ vi }.check Tr :ifTr=∅ then the algorithm end else jump ②。

②.Update each vertex’s “t-label” in Tr according to Nr for
v j ∈Tr , l jr)( ＝l jr- )1(for vi ∈ Nr ,if (li r)*( + wij )＜l jr)( then l jr)( ＝(li r)*( + wij ), Aj ＝{ vi }if (li r)*( + wij )＝l jr)( then Aj ＝ Aj ∪{ vi }set r←r+1, jump ①.

4. Experiment of the Improved Algorithm According to the improved Dijkstra’s “label algorithm”, this paper conducted an experiment. Fig. 1. Directed Graph Using the improved “label algorithm” to calculate the shortest path between v1 and other vertices in the above weighted digraph. The process is the following table:
Table 1. The Processing Process Experimental Analysis: A vertex may has many adjacent vertices. For example, v4 has 2 adjacent vertices: v1 and v3. All the shorted paths: v1→v2→v3→v6→v8 v1→v2→v5→v6→v8 (weight 6) v1→v2→v7 v1→v2→v3→v7 (weight 5) v1→v4 v1→v2→v3→v4 (weight 3) m.

Read More