Answer to Question #150974 in Algorithms for Hay

Question

5a
Discuss Djikstra’s algorithm explaining its relevance in today’s transportation
technology using artificial intelligence such as Uber and Bolt as a case.

Answer 1

In the public transportation system, all the bus stops and the landmark location acts as the nodes, and the link connecting two nodes are defined as the public road network, which is represented as G(N, E, R). where N={0, 1, 2, 3, 4....} denotes the set of all nodes , n denotes the number of nodes. The origin node and the destination node is represented as O, and D respectively.

Transit links$(E)=\{0 \leq e\leq m\}$ , m is number of links

Set of all bus lines $(R)=\{ 0, 1, 2, 3....n\}, n\epsilon N$

The basic mode of operation of Dijkstra's algorithm are given below:

1. Initial is D and P
2. Set S as an empty set.
3. Remaining vertices (V-S)

• initiate the shorting in (V-S) as per the current best estimation of their distance from the source.
• now, add the closest vertex u in (V-S), to S.
• Relax all the vertices which is still remaining in (V-S) and connected to u.

Where G(V,E) is the graph and V is the set of vertices and E is the set of edges.

S = the set of vertices whose shortest path already determined.

V-S = it is the remaining vertices.

D = Array of best estimates of shortest path

P It is the predecessors of each vertex.

Dijkstra's algorithm:

1. $D(S)\leftarrow 0$ (distance to source vertex is zero) for all $V\epsilon V-\{S\}$
2. do $D(V)\leftarrow \infty$ set all the remaining vertices infinite.
3. set S empty ( all the visited vertices is empty initially)
4. $Q\leftarrow V$ all the vertices are in queue initially, which is represented as Q.
5. while $(Q\neq empty)$ the empty of Q.
6. do $u\leftarrow minimum-distance$ select the element of Q with minimum distance.
7. $S\leftarrow S U\{ u\}$ , add u in the list of visited vertices.
8. for all $V\epsilon$ neighbors[u]
9. do if$(D[V]>D[u]+w(u,v) )$ if new shortest path found.
10. Then, $(D[V]\leftarrow D[u]+w(u,v) )$ , set the new value of the shortest path