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

    Join Date
    Mar 2015
    Posts
    40
    Rep Power
    6

    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.

    How to read two indices of previously read vertices (after creating adjacency matrix)?

    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 readGraph(GRAPH *pg);
    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);
    
    void readGraph(GRAPH *pg)
    {
        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;
        readGraph(&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. #2
  3. Contributing User

    Join Date
    Aug 2011
    Posts
    5,479
    Rep Power
    506
    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))
    //sqrt already exists.
    Last edited by b49P23TIvg; January 9th, 2016 at 08:23 AM.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo