Untitled

mail@pastecode.io avatar
unknown
plain_text
3 years ago
1.2 kB
6
Indexable
Never
#include<stdio.h>
#define MAX_Vertices 20
#define MAX_Length 20
#define MAX_Element 40
#define infinity 9999
typedef struct{
	int A[MAX_Vertices][MAX_Vertices];
	int n;
}Graph;
void init_Graph(Graph *G, int n){
	G->n=n;
	int i, j;
	for(i=1; i<=G->n; i++)
		for(j=1; j<=G->n; j++)
			G->A[i][j] = 0;
}
void add_edge(Graph *G, int x, int y, int z){
	G->A[x][y] = z;
	G->A[y][x] = z;
}

int pi[MAX_Vertices], p[MAX_Vertices], mark[MAX_Vertices];

void dijkstra(Graph *G, int s){
	int u, v, i;
	for(u=1; u<= G->n; u++){
		pi[u] = infinity;
		
		mark[u] = 0;
	}
	p[s] = -1;
	pi[s] = 0;
	for(u=1; u<=G->n; u++){
		int min_pi = infinity;
		for(i=1; i<=G->n; i++)
			if(mark[i] == 0 && pi[i] < min_pi){
				min_pi = pi[i];
				u = i;
			}
		mark[u] =1;
		for(v=1; v<=G->n; v++){
			if(G->A[u][v] != 0 && mark[v] ==0)
				if(pi[u] + G->A[u][v] < pi[v]){
					pi[v] = pi[u] + G->A[u][v];
					p[v] =u;
				}
		}
	}
}
int main(){
	Graph G;
	int n,m;
	freopen("dijkstra.txt", "r", stdin);
	scanf("%d%d", &n, &m);
	init_Graph(&G, n);
	int e, u, v, w;
		for(e=1; e<=m; e++){
			scanf("%d%d%d", &u, &v, &w);
			add_edge(&G, u, v, w);			
		}
	dijkstra(&G, 1);
	
	return 0;
}