Crossroads city problem

Hey guys!

I'm trying to find a solution to a crossing road problem i was given for practice. But i really hit a nail in it.
Basically i am given a graph and the weight of each path. And i have to findthe minimal time for which for example a person could get to the goal.

In example, you are given N villages you can pass, from 1 to N, and the M roads that connext each village(e.g the paths)

You give the program N and M. Then you give the program N - 2 numbers and the times for crossing the villages from 2 to N.

So what i get to acomplish is, i use dijkstra and find the shortest path, but what i fail to do is, find the time(e.g weight) it would take to cross this path and im a bit unsure how to exactly do it

My Code so far implementing dijkstra and finding shortest path.
*NOTE*: I know im using some C related code, but im looking for either C or C++ related help for implementing this.

  #include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define INF 1000000000
#define MAX 100
int G[MAX][MAX], c[MAX][MAX], U[MAX],
p[MAX],d[MAX],n,m;

void dijkstra(int r)
{
    int v , w, min ,i ,j;
    for(i =1; i<=n; i++) { U[i]=0; p[i]=r; d[i]=INF;}
    d[r]=p[r]=0;
    for(i=1;i<=n;i++)
    {
        v = 0; min = INF;
        for(j=1;j<=n;j++)
            if(U[j]==0 && d[j]<min) { v= j; min=d[j];}
        U[v]=1;
        for(j=1;j<=G[v][0];j++)
        {
            w=G[v][j];
            if(U[w] == 0 && d[v]+c[v][w]<d[w])
            { d[w]=d[v]+c[v][w]; p[w]=v;}
        }
    }
}

int main ()
{
    int u,v,w,i,j;
    scanf("%d %d %d", &n, &m);
    for(i=1;i<=n;i++) {
        G[i][0]=0; for(j=1;j<=n;j++)
        c[i][j]=INF; if(i==j)c[i][j]=0;
    }
    for(i =1; i<=m;i++) {
        scanf("%d %d %d", &u, &v, &w);
        G[u][++G[u][0]]=v; G[v][++G[v][0]] = u;
        c[u][v]=c[v][u]=w;
    }
    dijkstra(1); 
    for(i=1;i<=n;i++)
        printf("%d %d\n",i,p[i]);
    return 0;
}

Example Input :

Example Output :

Thanks to anyone who is willing to take his/her time to check this out and help me out!

Handy Andy (5051)

Hello FreeSocks,

You should decide if you want C or C++ code. Mixing the two is not always a good idea, but works sometimes.

For a start compare this to what you have posted.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

#pragma warning(disable : 4996) // <--- Needed for my IDE/compiler.

//#define INF 1000000000
//#define MAX 100

constexpr size_t MAX{ 100 }; // <--- Or const size_t MAX = 100;. Pre C++11 Standards.
constexpr size_t INF{ 1000000000 };

int G[MAX][MAX], c[MAX][MAX], U[MAX],  // <--- Best not to useglobal variables.
p[MAX], d[MAX], n, m;

void dijkstra(int r)
{
	int v, w, min, i, j;

	for (i = 1; i <= n; i++)
	{
		U[i] = 0; p[i] = r; d[i] = INF;
	}

	d[r] = p[r] = 0;

	for (i = 1; i <= n; i++)
	{
		v = 0; min = INF;

		for (j = 1; j <= n; j++)
			if (U[j] == 0 && d[j] < min)
			{
				v = j;
				min = d[j];
			}
		U[v] = 1;

		for (j = 1; j <= G[v][0]; j++)
		{
			w = G[v][j];

			if (U[w] == 0 && d[v] + c[v][w] < d[w])
			{
				d[w] = d[v] + c[v][w]; p[w] = v;
			}
		}
	}
}

int main()
{
	int u, v, w, i, j;
	//int G[MAX][MAX], c[MAX][MAX], U[MAX], // <--- Should be here and passed to the function.
	//	p[MAX], d[MAX], n, m;

	scanf("%d %d %d", &n, &m); // <--- Do you need a third variable of one less %d?

	for (i = 1; i <= n; i++)
	{
		G[i][0] = 0;
		
		for (j = 1; j <= n; j++)
			c[i][j] = INF;
		
		if (i == j)c[i][j] = 0; // <--- Is this part of the inner for loop or the outer for loop?
	}

	for (i = 1; i <= m; i++)
	{
		scanf("%d %d %d", &u, &v, &w);

		G[u][++G[u][0]] = v; G[v][++G[v][0]] = u;

		c[u][v] = c[v][u] = w;
	}

	dijkstra(1);

	for (i = 1; i <= n; i++)
		printf("%d %d\n", i, p[i]);

	return 0;
}

Notice comments on lines 57 and 66.

What you have works for the compiler, but is hard to read. When you write code is is best to write it in a way the makes it easy to read for a person. The compiler does not care about white space or blank lines.

When you are given instructions for a program with variables like "N" and "M" that is fine for instructions. If "N" represents villages then call your variable "villages" not "N" and for "M" call it "roads". It makes your code easier to follow and easier to understand. It has been said that a variable should be a noun. To that I add it should describe what it is or does.

Note:

for(i=1;i<=n;i++) {
        G[i][0]=0; for(j=1;j<=n;j++)
        c[i][j]=INF; if(i==j)c[i][j]=0;
    }

This may work for the compiler, but it is hard to understand when trying to read it.

A for loop without {}s only includes the next line until it finds a semicolon anything after that is not considered part of the for loop unless it is in a set of {}s.

So what the code actually looks like with blank lines and proper indenting is:

for (i = 1; i <= n; i++)
{
	G[i][0] = 0;
		
	for (j = 1; j <= n; j++)
		c[i][j] = INF;
		
	if (i == j)c[i][j] = 0; // <--- Is this part of the inner for loop or the outer for loop?
}

Notice how line 8 becomes part of the outer for loop and not the inner for loop.

I have yet to run the program because of the compile errors left and the question about the above code.

I will work on that part shortly and let you know what I find.

Hope that helps for now,

Andy

FreeSocks (35)

@Handy Andy

Thank you for your reply. I wrote it really quick and didn't pay attention to some stuff.
I can note that Line 8 at the bottem does in fact work in the outer loop, the inner loop only works for c[i][j] = INF; The if statement is for the outter loop as was my intention

I have reformatted the code and left some comments out on teh scans , so you can get better idea of what i mean.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define INF 1000000000
#define MAX 100
int G[MAX][MAX], c[MAX][MAX], U[MAX],
p[MAX],d[MAX],n,m;

void dijkstra(int r)
{
    int v , w, min ,i ,j;
    for(i =1; i<=n; i++) 
    {
         
         U[i]=0; p[i]=r; d[i]=INF;
         
    }
    d[r]=p[r]=0;

    for(i=1;i<=n;i++)
    {
            v = 0; min = INF;
        for(j=1;j<=n;j++) 
        {
                if(U[j]==0 && d[j]<min) 
                { 
                    v= j; min=d[j];
                }
            U[v]=1;
            for(j=1;j<=G[v][0];j++)
            {
                w=G[v][j];
                if(U[w] == 0 && d[v]+c[v][w]<d[w])
                {
                    d[w]=d[v]+c[v][w]; 
                    p[w]=v;
                }
            }
        }
    }

}
int main ()
{
    int u,v,w,i,j,z,x,y;
    
    //n = number of villages and m = number of paths between villages : 5 and 8 from the example input
    scanf("%d %d", &n, &m);
    //z,x,y the different times to go through villages : 25 30 30 from the example input
    scanf("%d %d %d", &z, &x, &y);
    for(i=1;i<=n;i++) 
    {
        G[i][0]=0; 
        for(j=1;j<=n;j++)
        {
            c[i][j]=INF; 
        }
        if(i==j)
        {
            c[i][j]=0;
        }
    }

    for(i =1; i<=m;i++) 
    {
        /*u is the village node, v is the target village node, w is the time to travel from one node to another
(e.g the weight of the path in graph term) : 1 3 100, 1 2 80 , 1 4 20  - From example input*/
        scanf("%d %d %d", &u, &v, &w);
        G[u][++G[u][0]]=v; 
        G[v][++G[v][0]] = u;
        c[u][v]=c[v][u]=w;
    }
    //runs dijkstra from the first node. E.g finds the shortest path from village node 1.
    dijkstra(1); 
    //prints the shortest path
    for(i=1;i<=n;i++)
    {
        printf("%d %d\n",i,p[i]);
    }
    return 0;
}

Last edited on

Topic archived. No new replies allowed.

C++

Forum

Crossroads city problem