Question

One simple representation for a graph is to use an adjacency matrix: each of the N nodes is given a unique number in the range 0 to N-1 to identify it. A large two dimensional array A with N rows and N columns is created so that A[x][y] stores the cost of travelling directly from node x to node y. if A[x][y] is zero, then there is no direct connection from x to y. A[x][y] does not need to equal A[y][x] - there can be one-way links. Assume that a priority queue exactly as you described for part A has been implemented, and you can use it. Also assume that an adjacency matrix as just described has been created for an N node graph, and you can use it too. Write a function that finds the length of the shortest path (or the cost of the cheapest path) between nodes S and D, which are provided as parameters.

must be in C++ code

Answer 1

GIVEN:

write a C++ code to find the length of the shortest path ( or the cost of the cheapest path ) between nodes S and D, which are provided as parameters. Adjacency matrix has been created for N node graph. A large two dimentional array A with N rows and N columns.

A[x][y] stores the cost of travelling directly from node x to node y.

// Adjacency matrix representation

#include<iostream>

#include<stdio.h>

using namespace std;

#define max 6

void dijkstra ( int G[max,max], int d, int s );

int main ( ) {

int d = 6;

int s = 0;

dijkstra (G,d,s);

return 0;

}

void dijkstra(G[max][max], int d, int s)  

{

int A[x][y], distance [max], pred[max];

int visited [max], count, mdistance, nextnode, i, j;

for( i=0;i<n;i++)

for( j=0;j<n;j++)

if (G[ i ][ i ]==0)

A[ i ][ j ] =INFINITY;

else

A[ i ][ j ] = G[ i ][ j ];

for ( i=0;i<n;i++) {

distance [ i ] =cost [s][ i ];

pred[ i ] =s ;

visited [ i ] =0;

}

distance [ s ] =0;

visited [ s ]=1;

count =1;

while ( count<n-1 ) {

mdistance = INFINITY;

for ( i=0;i<n;i++)

if (distance[ i ] < mdistance&&! visited[ i ] )

{

mdistance = distance [ i ]

nextnode = i;

}

visited [nextnode ] =1;

for( i=0;i<n;i++)

if ( !visited [ i ] )

if ( mdistance + cost [nextnode ][ i ];

pred[ i ] = nextnode;

}

count ++;

}

for ( i=0;i<n;i++)

if ( i!= s ) {

cout<< " \n distance of node " << i << "= " << distance [ i ];

cout << "\n path ="<< i;

j=i;

do {

j= pred [ j ];

cout<< "< - " << j;

}

while ( j! = s);

}

}