### Thread: C: Shortest path in a graph between two vertices

1. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Mar 2015
Posts
44
Rep Power
8

#### C: Shortest path in a graph between two vertices

Write a program that will print adjacency matrix of a directed and weighted graph.
Weights are positive real values, and graph is strongly connected.
Then, print values of two vertices which indices are read (values of each vertice are functions: sin(index),cos(index),index^2,sqrt(index)).

How to check if a graph is strongly connected? I found some algorithms for strongly connected components of a graph (Tarjan's algorithm and Kosaraju's algorithm),
but can't figure out how to implement them with using only standard libraries.

Here is the unfinished code:
Code:
```#include <stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAX 10
#define PI 3.14

typedef struct
{
int vertices;//number of vertices
int edges;//number of edges
int u,v;//index of current and next node
double w;// positive weights
double nodes[MAX];//data of one node/vertice are all defined *math. functions
double w_mat[MAX][MAX];//weight matrix
}GRAPH;

void printWMatrix(GRAPH *pg);
void FLOYD(GRAPH *pg);//Floyd's algorithm for shortest path
void printPath(GRAPH *pg);

//*math. functions
double temp_sin(int x);
double temp_cos(int x);
double temp_pow(int x);
double temp_sqrt(int x);

{
do
{
printf("Number of vertices: ");
scanf("%d",&pg->vertices);
}
while(pg->vertices <= 0 || pg->vertices > MAX);
do
{
printf("Number of edges: ");
scanf("%d",&pg->edges);
}
while(pg->edges <= 0);
int i,j;
for(i=0; i<pg->vertices; i++)
for(j=0; j<pg->vertices; j++)
pg->w_mat[i][j]=0;
printf("(u,v,w): \n");
for(i=0; i<pg->edges; i++)
{
do
{
scanf("%d %d %lf",&pg->u, &pg->v, &pg->w);
pg->w_mat[pg->u][pg->v]=pg->w;
}
while(pg->w <= 0);
}
}

void printPath(GRAPH *pg)
{
int i,j;
for(i=0; i<pg->vertices; i++)
{
//for each node, print math. functions
}
}

void FLOYD(GRAPH *pg)
{
int i,j,k;
for(k=0; k<pg->vertices; k++){
for(i=0; i<pg->vertices; i++){
for(j=0; j<pg->vertices; j++){
if(pg->w_mat[i][j] > pg->w_mat[i][k] + pg->w_mat[k][j])
pg->w_mat[i][j]=pg->w_mat[i][k] + pg->w_mat[k][j];
}
}
}
printPath(pg);
}

void printWMatrix(GRAPH *pg)
{
int i,j;
for(i=0; i<pg->vertices; i++)
{
for(j=0; j<pg->vertices; j++)
printf("%4.2lf ",pg->w_mat[i][j]);
printf("\n");
}
printf("\n");
}

double temp_sin(int x)
{
double res;
double t=x*PI/180;
res=sin(t);
return res;
}
double temp_cos(int x)
{
double res;
double t=x*PI/180;
res=cos(t);
return res;
}
double temp_pow(int x)
{
double res;
res=pow(x,2);
return res;
}
double temp_sqrt(int x)
{
double res;
res=sqrt(x);
return res;
}

int main()
{
GRAPH pg;
printWMatrix(&pg);

/*printf("Read two indices of existing vertices: \n");
do
{
printf("(u,v): \n");
scanf("%d %d",&pg.u, &pg.v);
}
while(pg.u < 0 || pg.v < 0);*/

//FLOYD(&pg);
return 0;
}```
2. Wow! Big improvement. main() included, and it works.
Incomplete, however.
I understand that a strongly connected graph is one in which all nodes can be reached from any node.
So the simplest strongly connected test is to traverse the graph starting from each node. If all nodes can be reached from each start point the graph is strongly connected. Simple is appropriate if you have no more than 10 nodes.
I do not understand this "print values of two vertices which indices are read (values of each vertice are functions: sin(index),cos(index),index^2,sqrt(index))." instruction. Hope you do.

The weights are positive, you can use Dijkstra's algorithm.
Dijkstra's algorithm - Rosetta Code
#ifndef M_PI
#define M_PI 3.14
#endif
//*math. functions
#define D2R(X) ((X)*(M_PI/180)) /* convert degrees to radians */
#define SIND(X) (sin(D2R(X))) /* SIND evaluates sin of argument in degrees */
#define COSD(X) (cos(D2R(X)))
#define SQUARE(X) ((X)*(X))