## Example: Dijkstra Algorithm

Here we want to find the best route between A and E (see below). You can see that there are six possible routes between A and E (ABE, ACE, ABDE, ACDE, ABDCE, ACDBE), and it's obvious that ABDE is the best route because its weight is the lowest. But life is not always so easy, and there are some complicated cases in which we have to use algorithms to find the best route.

- As you see in the first image, the source node (A) has been chosen as T-node, and so its label is permanent (we show permanent nodes with filled circles and T-nodes with the --> symbol).
- In the next step, you see that the status record set of tentative nodes directly linked to T-node (B, C) has been changed. Also, since B has less weight, it has been chosen as T-node and its label has changed to permanent (see below).
- In step 3, like in step 2, the status record set of tentative nodes that have a direct link to T-node (D, E), has been changed. Also, since D has less weight, it has been chosen as T-node and its label has changed to permanent.
- In step 4, we don't have any tentative nodes, so we just identify the next T-node. Since E has the least weight, it has been chosen as T-node.

Lastly, E is the destination, so we stop here.

Advertisement

We are at end! Now we have to identify the route. The previous node of E is D, and the previous node of D is B, and B's previous node is A. So the best route is ABDE. In this case, the total weigh is **4** (1+2+1).

Although this algorithm works well, it's so complicated that it may take a long time for routers to process it, and the efficiency of the network fails. Also, if a router gives the wrong information to other routers, all routing decisions will be ineffective. To understand this algorithm better, here is the source of program written by C:

#define MAX_NODES 1024 /* maximum number of nodes */ #define INFINITY 1000000000 /* a number larger than every maximum path */ int n,dist[MAX_NODES][MAX_NODES]; /*dist[I][j] is the distance from i to j */ void shortest_path(int s,int t,int path[ ]) {struct state { /* the path being worked on */ int predecessor ; /*previous node */ int length /*length from source to this node*/ enum {permanent, tentative} label /*label state*/ }state[MAX_NODES]; int I, k, min; struct state * p; for (p=&state[0];p < &state[n];p++){ /*initialize state*/ p->predecessor=-1 p->length=INFINITY p->label=tentative; } state[t].length=0; state[t].label=permanent ; k=t ; /*k is the initial working node */ do{ /* is the better path from k? */ for I=0; I < n; I++) /*this graph has n nodes */ if (dist[k][I] !=0 && state[I].label==tentative){ if (state[k].length+dist[k][I] < state[I].length){ state[I].predecessor=k; state[I].length=state[k].length + dist[k][I] } } /* Find the tentatively labeled node with the smallest label. */ k=0;min=INFINITY; for (I=0;I < n;I++) if(state[I].label==tentative && state[I].length < min)=state[I].length; k=I; } state[k].label=permanent }while (k!=s); /*Copy the path into output array*/ I=0;k=0 Do{path[I++]=k;k=state[k].predecessor;} while (k > =0); }