Archive for the ‘Bellman Ford’s’ Category

UVA – 10816 – Travel in Desert   1 comment


The problem here is asking us to find the shortest path between two nodes in a graph, under constraint that the maximum temperature of any edge used in this path is minimum.
I’ll explain two ways to solve this problem

One way would be using floyd warshall’s first to determine the minimum temperature of the path, then we build a graph using only the edges that have temperature <= minimum temperature if there's more than one edge having this property between two nodes its obvious that we should use the one with minimum weight (since we'll be looking for the shortest path), then we use floyd warshall's again or any other shortest path algorithm to find the distance between the start and destination in this new graph, see implementation for more details.

Another way would be to binary search on the minimum temperature and use any shortest path algorithm to find the shortest path between start and destination bellman ford should be a good choice as its easy to implement and will handle the problem of the multiple edges between two nodes automatically.
Both methods have almost the same running time O(V^3) vs. O(VE log 300)

You may notice that in the second way we don’t really have to run bellman ford inside the binary search instead we may run a simple O(V+E) dfs to check that destination is reachable from start that would make the running time O(VE).

#include <stdio.h>
#define inf 1e9
int a, b;
int s[10005], t[10005];
float dp[105][105];
int path[105][105];
float r[10005], d[10005];
float max(float a,float b){return (a>b)?a:b;}
float min(float a,float b){return (a<b)?a:b;}
float absval(float a){return (a<0)?-a:a;}
void printPath(int i, int j, char p) {
	if (!path[i][j]) {
		if (!p)
			printf("%d ", i);
		printf("%d", j);
		if (j != b)//if j is not the final node
			putchar(' ');
	} else {
		printPath(i, path[i][j], p);
		printPath(path[i][j], j, 1);
	}
}
int main() {
	int n, e, i, j, k;
	while (scanf("%d %d", &n, &e) == 2) {
		scanf("%d %d", &a, &b);
		for (i = 1; i <= n; i++)
			for (j = 1; j <= n; j++)
				dp[i][j] = inf;
		for (i = 0; i < e; i++) {
			scanf("%d %d %f %f", s + i, t + i, r + i, d + i);
			dp[s[i]][t[i]] = min(dp[s[i]][t[i]],r[i]);
			dp[t[i]][s[i]] = min(dp[t[i]][s[i]],r[i]);
		}
		//use floyd warshall to find the lowest tempreture
		for (k = 1; k <= n; k++)
			for (i = 1; i <= n; i++)
				for (j = 1; j <= n; j++)
					dp[i][j] = min(dp[i][j],max(dp[i][k],dp[k][j]));
		float minTemp = dp[a][b];
		//refill floyd warshall array with edge weights
		//given each edge has minimum weight and tempreture less than lowest tempreture
		for (i = 1; i <= n; i++)
			for (j = 1; j <= n; j++) {
				dp[i][j] = inf;
				path[i][j] = 0;
			}
		for (i = 0; i < e; i++) {
			if (r[i]<minTemp+1e-6) {
				//if there are multiple edges between two nodes,greedily choose the one with smaller length
				dp[s[i]][t[i]] = min(dp[s[i]][t[i]],d[i]);
				dp[t[i]][s[i]] = min(dp[t[i]][s[i]],d[i]);
			}
		}
		//floyd warshall again but this time we'll store the intermidate node for each two nodes to allow path retrival
		for (k = 1; k <= n; k++)
			for (i = 1; i <= n; i++)
				for (j = 1; j <= n; j++)
					if (dp[i][j] > dp[i][k] + dp[k][j]) {
						dp[i][j] = dp[i][k] + dp[k][j];
						path[i][j] = k;
					}
		printPath(a, b, 0);
		putchar('\n');
		printf("%.1f %.1f\n", dp[a][b], minTemp);
	}
	return 0;
}

Advertisements

Posted June 12, 2012 by epicrado in Bellman Ford's, Floyd warshall, Graphs

UVA – 558 – Wormholes   Leave a comment


#include <stdio.h>
#include <stdlib.h>
typedef struct Edge
{
	int s,t,w;
}wormhole;
wormhole map[2200];
int d[1100];
char solve(int n,int e)
{
	int i,j;
	d[0] = 0;
	for(i=0;i<n-1;i++)
		for(j=0;j<e;j++)
			if(d[map[j].s] + map[j].w < d[map[j].t])
				d[map[j].t] = d[map[j].s] + map[j].w;
	for(j=0;j<e;j++)
			if(d[map[j].s] + map[j].w < d[map[j].t])
				return 1;
	return 0;
}
int main()
{
	int c,n,m,i;
	int top = 0;
	scanf("%d",&c);
	while(c-->0)
	{
		top = 0;
		scanf("%d %d",&n,&m);
		for(i=0;i<n;i++)
			d[i] = 1<<20;
		for(top=0;top<m;top++)
			scanf("%d %d %d",&map[top].s,&map[top].t,&map[top].w);
		if(solve(n,top))
			printf("possible\n");
		else
			printf("not possible\n");

	}
	return 0;
}

Posted August 14, 2011 by epicrado in Bellman Ford's