Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.2 kB
2
Indexable
Never
#include<stdio.h>
#define MAX_N 100
#define NO_EDGE -1
#define oo 9999
typedef struct {
	int n, m, w;
	int W[MAX_N][MAX_N];
} Graph;

void init_graph(Graph *pG, int n) {
	int u, v;
	pG->n = n;
	for(u = 1; u <= n; u++) 
		for(v = 1; v <= n; v++)
			pG->W[u][v] = NO_EDGE;
}

void add_edge(Graph *pG, int u, int v, int w) {
	pG->W[u][v] = w;
}

int mark[MAX_N];
int pi[MAX_N];
int p[MAX_N];

void MooreDijkstra(Graph *pG, int s) {
	int u, v, j, it;
	for(u = 1; u <= pG->n; u++) {
		pi[u] = oo;
		mark[u] = 0;
	}
	pi[s] = 0;
	p[s] = -1;
	for(it = 1; it < pG->n; it++) {
		int min_pi = oo;
		for(j = 1; j <= pG->n; j++) 
			if(mark[j] == 0 && pi[j] < min_pi) {
				min_pi = pi[j];
				u = j;
			}
		mark[u] = 1;
		for(v = 1; v <= pG->n; v++)
			if(mark[v] == 0 && pG->W[u][v] != NO_EDGE)
				if(pi[v] > min_pi + pG->W[u][v]) {
					pi[v] = min_pi + pG->W[u][v];
					p[v] = u;
				}
	}
}

int main() {
	Graph G;	
	int n, m, u, v, w, i;
	scanf("%d%d", &n, &m);
	init_graph(&G, n);
	for(i = 0; i < m; i++) {
		scanf("%d%d%d", &u, &v, &w);
		add_edge(&G, u, v, w);
	}
	MooreDijkstra(&G, 1);
	for(u = 1; u <= G.n; u++)
		printf("pi[%d] = %d, p[%d] = %d\n", u, pi[u], u, p[u]);
	return 0;
}