چکیده (انگلیسی):

The networks of the present day communication systems, be it a public road transportation system or a
MANET or an Adhoc Network, frequently face a lot of uncertainties in particular regarding traffic jam, flood
or water logging or PWD maintenance work (in case of public road network), attack or damage from internal
or external agents, sudden failure of one or few nodes. Consequently, at a real instant of time, the existing
links/arcs of a given network (graph) are not always in their original/excellent condition physically or
logically, rather in a weaker condition, or even sometimes disabled or blocked temporarily and waiting for
maintenance/repair; and hence ultimately causing delay in communication or transportation. We do not take
any special consideration if few of the links be in a better condition at the real time of communication, we
consider only such cases where few links are in inferior condition (partially or fully damaged). The classical
Dijkstra’s algorithm to find the shortest path in graphs is applicable only if we assume that all the links of the
concerned graph are available at their original (ideal) condition at that real time of communication, but at real
time scenario it is not the case. Consequently, the mathematically calculated shortest path extracted by using
Dijkstra’s algorithm may become costlier (even in-feasible in some cases) in terms of time and/or in terms of
other overhead costs; whereas some other path may be the most efficient or most optimal. Many real life
situations of communication network or transportation network cannot be modeled into graphs, but can be well
modeled into multigraphs because of the scope of dealing with multiple links (or arcs) connecting a pair of
nodes. The classical Dijkstra’s algorithm to find the shortest path in graphs is not applicable to multigraphs. In
this study the authors make a refinement of the classical Dijkstra’s algorithm to make it applicable to directed
multigraphs having few links partially or fully damaged. We call such type of multigraphs by GRTmultigraphs
and the modified algorithm is called by Dijkstra’s Algorithm for GRT-Multigraphs (DA-GRTM,
in short). The DA-GRTM outputs the shortest paths and the corresponding min cost in a GRT-multigraph at
real time and thus the solution is a real time solution, not an absolute solution. It is claimed that DA-GRTM
will play a major role in the present day communication systems which are in many cases giant networks, in
particular in those networks which cannot be modeled into graphs but into multigraphs.