# Untitled

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);