Question

How to print the shortest path in multigraph java code ?with example

Answer 1

Now, to solve this problem we need to see the definition of what a multigraph is, so we see it from the perspective of graph theory and we have a graph with two important properties -

1) There will be multiple edges between a given set of nodes, for example, in a city, there are multiple times a scenario where you have over and under the bridge scenarios. We represent that as e1(a,b),e2(a,b).

2) Now there can be two meanings of multiple edges it's either two separate edges which means they have unique properties or they are unique by the means that the same is passed on twice in a path and is considered as two separate edges.

Now there are multiple attempts to solve this problem but the one that will work is, using Dynamic Programming.

The Basic Idea - You have a starting point let's say A and you have a graph and have to reach till 'G' to do that properly, we'll have let's say A connected to 3 nodes, B, C, D and then they are connected to E and F or both, and then that is connected to G directly or H and then G.

If you can see there are multiple, paths possible by choosing or taking one or the other decision. Dynamic Programming keep things in an updated manner as soon as things start to appear in the context ot tracing the graph, details of each step is explained below -

class multigraph {

   static int count = 7; // we can choose how many nodes are available

static int max = 999999; // just a number extremely huge working as infinity

public static int closestdest(int[][] plot) // the matrix is given carrying the value of edge weight

{

int distance[] = new int[count];

          dist[count - 1] = 0;

// Now here we have to remember even when we are trying to figure out the value of A to G we'll start from G and see if the nodes just a level (its immediate neighbor is one with only one edge) ahead at N-2, will be evaluated and see which is the best option if we have all the option and update the distance array.

  

for (int i = count - 2; i >= 0; i--)

{ distance[i] = 999999; / / initally all points which aren't connected are at a infinite distance  

for (int j = i; j < count; j++)

{ if (plot[i][j] == INF) { continue;} // happens is distance is 999999 which means no edge

distance[i] = Math.min(distance[i], plot[i][j] + distance[j]);             }         }

return distance[0];

    }

// The distance formula here is a pretty simple one, it's like if we have a direct connection and alternative, take the one minimum of those two. See the reason it works is, for level N-1 we have a direct edge, so' one of the connecting directly is chosen, next level has only to measure the minimum of N-2 edge plus distance of where it lands on N-1 and that is why we have the minimum of two option in the second last line

All we have to do now, to run this program is to give the problem a graph and it will work, just by typing

closestdest(graph_name);

Any doubts ask in comments