1693: 图-最短路径-Dijkstra
金币值：2
定数：9
时间限制：1.000 s
内存限制：128 M
解决：7
提交：26
正确率：26.92% 命题人：
题目描述
已知一个加权有向图，给出图中从某个顶点到其它各个顶点的最短路径。要求存储结构用邻接矩阵，应用迪杰斯特拉方法设计算法。
例如，有了一张自驾旅游路线图，就会知道城市间的高速公路长度。路径导航程序就会帮助游客寻找一条出发地与目的地之间的最短路径。
阅读分析下列程序，请编写Dijkstra()函数代码。
例如，有了一张自驾旅游路线图，就会知道城市间的高速公路长度。路径导航程序就会帮助游客寻找一条出发地与目的地之间的最短路径。
阅读分析下列程序，请编写Dijkstra()函数代码。
#include<stdio.h>
#define MAXVEX 100 // 最大顶点数由用户定义
#define INFINITY 65535
typedef char VertexType; // 顶点类型应由用户定义
typedef int EdgeType; // 边上的权值类型应由用户定义
typedef struct {
VertexType vexs[MAXVEX];
EdgeType arc[MAXVEX][MAXVEX];
int numNodes;
int numEdges;
} MGraph;
int label[MAXVEX]; // 存储从源点出发到其余各个顶点的最短路径上的最后一个顶点编号
int distance[MAXVEX]; // 存储从源点出发到其余各个顶点的最短距离
void CreateGraph(MGraph &G) {
int i,j,k,w;
for(i=0; i<G.numNodes; i++) // 初始化邻接矩阵
for(j=0; j<G.numNodes; j++) G.arc[i][j] = INFINITY;
for(k=0; k<G.numEdges; k++) { // 输入边信息填写有向图的邻接矩阵
scanf("%d %d %d",&i,&j,&w); // 边的信息包括顶点1，顶点2以及它们之间的距离
G.arc[i][j] = w;
}
}
void Output(int n, int v) {
for(int i=0; i<n; i++) { //按照指定格式输出从源点v到其余各点的最短距离及其路径
if(i!=v) {
printf("v%d-v%d:%d[v%d",v,i,distance[i],i);
for(int u=i; u!=v; u=label) printf("<-v%d",label);
printf("]\n");
}
}
}
int main(void) {
void Dijkstra(MGraph G, int v);
MGraph graph;
scanf("%d %d",&graph.numNodes,&graph.numEdges);
CreateGraph(graph); //存储结构是邻接矩阵
Dijkstra(graph, 0); //求从顶点0出发到其余各个顶点的最短距离及其路径
Output(graph.numNodes, 0); //打印从顶点0出发到其余各个顶点的最短距离及其路径
return 0;
}
/*提交以下代码*/
void Dijkstra(MGraph G, int v) { //求从顶点v出发到其它各顶点的最短距离
} 输入
第1行输入2个整数，分别表示图中的顶点数n和边数m
第2-m+1行每行输入3个整数，分别表示图中每条有向边的起点i，终点j和权值weight（顶点编号从0开始）
第2-m+1行每行输入3个整数，分别表示图中每条有向边的起点i，终点j和权值weight（顶点编号从0开始）
输出
共有n-1行，每行前3个数据分别表示图中源点编号（假设编号为0的顶点是图中的源点）、其它顶点编号以及这两个顶点之间的路径长度，后面的数据表示这条路径上的顶点编号（从终点编号出发到源点编号结束）。
样例输入 复制
9 16
0 1 1
0 2 5
1 2 3
1 3 7
1 4 5
2 4 1
2 5 7
3 4 2
3 6 3
4 5 3
4 6 6
4 7 9
5 7 5
6 7 2
6 8 7
7 8 4样例输出 复制
v0-v1:1[v1<-v0]
v0-v2:4[v2<-v1<-v0]
v0-v3:8[v3<-v1<-v0]
v0-v4:5[v4<-v2<-v1<-v0]
v0-v5:8[v5<-v4<-v2<-v1<-v0]
v0-v6:11[v6<-v4<-v2<-v1<-v0]
v0-v7:13[v7<-v5<-v4<-v2<-v1<-v0]
v0-v8:17[v8<-v7<-v5<-v4<-v2<-v1<-v0]提示
v0-v2:4[v2<-v1<-v0]表示v0到v2的最短距离为4，[]内输出的是最短路径，即v0通过v1到达v2
算法基本思想
1. 定义标志数组，距离数组，标号数组（前驱结点）等相关变量，请考虑为什么定义这些数组？与最小生成树中lowcost数组和closet数组之间有什么关系？
2. 初始化标志数组，距离数组，标号数组
3. 循环n-1次
3.1 在距离数组中查找最短的距离，设第index个顶点的路径距离最小
3.2 修改标志数组中第index个元素
3.3 更新距离数组以及标号数组
算法基本思想
1. 定义标志数组，距离数组，标号数组（前驱结点）等相关变量，请考虑为什么定义这些数组？与最小生成树中lowcost数组和closet数组之间有什么关系？
2. 初始化标志数组，距离数组，标号数组
3. 循环n-1次
3.1 在距离数组中查找最短的距离，设第index个顶点的路径距离最小
3.2 修改标志数组中第index个元素
3.3 更新距离数组以及标号数组
void Dijkstra(MGraph G, int v) { //求从顶点v出发到其它各顶点的最短距离
int n=G.numNodes;
bool visited[MAXVEX];
for (int i = 0; i < n; i++) {
//初始化访问数组
//初始化距离数组
//初始化标签数组
}
visited[v]=true;
for (int i = 1; i < n; i++) {
int min=INFINITY; //查找最短的距离
int index;
for (int j = 0; j < n; j++) {
if() {
}
}
visited[index]=true;
for (int j = 0; j < n; j++) { //更新
if () {
}
}
}
}