typedef struct gra{ //顶点
int val;
int weight;
}graph;
graph g[1005][1005],dist[1005]; //图 和 最短路径
int visit[1005]; //顶点是否已被访问
void dijkstra(int start,int n){
int min,u;
for(int i=1;i<=n;i++){ //初始化最短路径数组 和 访问数组
dist[i].val = MAXVAL;
visit[i]=0;
}
for(int i=1;i<=n;i++){ //计算源点到各顶点的最短路径
if(g[start][i].val < MAXVAL){
dist[i].val = g[start][i].val;
dist[i].weight = g[start][i].weight;
}
}
visit[start] = 1; //设置源点已被访问
dist[start].val = 0; //源点到源点的距离为0
for(int i=1;i<=n;i++){ //计算n轮后最短路径
min = MAXVAL;
u = 0;
for(int k=1;k<=n;k++){ //找出每一轮新的最短路径的顶点
if(visit[k]==0 && dist[k].val < min){
min = dist[k].val;
u = k; //设置该顶点为新的起点
}
}
visit[u] = 1; //设置该顶点已被访问
for(int j=1;j<=n;j++){ //以新顶点为起点,更新最短路径
if(visit[j]==0 && dist[j].val > (dist[u].val + g[u][j].val)){//如果 源点到新起点的距离 加上 新起点到各点的距离,比 源点 到 各点 的距离短,更新最短路径
dist[j].val = dist[u].val + g[u][j].val;
dist[j].weight = dist[u].weight + g[u][j].weight;
}else if(visit[j]==0 && dist[j].val == (dist[u].val + g[u][j].val)){//如果距离相等,则选择花费较小的路径作为最短距离
if(dist[j].weight > (dist[u].weight + g[u][j].weight)){
dist[j].weight = dist[u].weight + g[u][j].weight;
}
}
}
}
}