PTA：jmu-ds-最短路径
给定一个有向图，规定源点为0，求源点0到其他顶点最短路径。###你要实现的 函数接口定义：
void Dijkstra(MGraph g,int v);//源点v到其他顶点最短路径 裁判测试程序样例：
#include <stdio.h>
#include <iostream>
#define MaxSize 100
#define INF 32767 //INF表示∞
#define MAXV 100 //最大顶点个数
using namespace std;
/*有向图的邻接矩阵,顶点编号0开始 */
typedef struct //图的定义
{ int **edges; //邻接矩阵int n,e; //顶点数，弧数
} MGraph; //图的邻接矩阵表示类型
void CreateMGraph(MGraph &g,int n,int e );//n为顶点数，e为边数，g为有向图
void Dispath(int dist[],int path[],int s[],int n,int v);
/*输入最短路径，dist各顶点最短距离，path最短路径前驱，n顶点数，v源点 */
void Dijkstra(MGraph g,int v); //源点v到其他顶点最短路径
void Ppath(int path[],int i,int v); //前向递归查找路径上的顶点
void PrintMGraph(MGraph g); //输出邻接矩阵，释放内存
int main()
{MGraph g;int n,e;cin>>n>>e;CreateMGraph(g,n,e );//PrintMGraph(g);Dijkstra(g,0); return 0;
}void CreateMGraph(MGraph &g,int n,int e )
{int i,j,a,b,weight;g.edges=new int *[n]; for(i=0;i<n;i++) g.edges[i]=new int[n];for(i=0;i<n;i++)for(j=0;j<n;j++)g.edges[i][j]=INF;for(i=1;i<=e;i++){cin>>a>>b>>weight;g.edges[a][b]=weight;}g.n=n;g.e=e;
}
void PrintMGraph(MGraph g)
{int i,j;for(i=0;i<g.n;i++){for(j=0;j<g.n;j++) cout<<g.edges[i][j]<<" ";cout<<endl;}for(i=0;i<g.n;i++) delete[] g.edges[i];
}
void Ppath(int path[],int i,int v) //前向递归查找路径上的顶点
{int k;k=path[i];if (k==v) return; //找到了起点则返回Ppath(path,k,v); //找顶点k的前一个顶点printf(" %d",k); //输出顶点k
}
void Dispath(int dist[],int path[],int s[],int n,int v)
{int i;for (i=0;i<n;i++)if (s[i]==1&&i!=v) { printf("从%d到%d的最短路径长度为:%d,路径为:",v,i,dist[i]);printf("%d",v); //输出路径上的起点Ppath(path,i,v); //输出路径上的中间点printf(" %d",i); //输出路径上的终点cout<<endl;}else if(s[i]==0)printf("从%d到%d不存在路径\n",v,i);
}
/* 请在这里填写答案 */输入样例：
输入顶点数、边数，再依次输入每条边的2个邻接点编号（顶点编号从0开始）及权值。
5 7
0 1 10
0 4 100
0 3 30
1 2 50
2 4 10
3 2 20
3 4 60
输出样例：
若2个顶点不存在路径，则输出从3到7不存在路径
从0到1的最短路径长度为:10,路径为:0 1
从0到2的最短路径长度为:50,路径为:0 3 2
从0到3的最短路径长度为:30,路径为:0 3
从0到4的最短路径长度为:60,路径为:0 3 2 4做题思路：
根据所学知识，要求最短路径的话，应该使用Dijkstra 算法来计算从源点 0 到图中所有其他顶点的最短路径。（Dijkstra 算法是一种贪心算法，用于计算带权有向图中单个源点到所有其他顶点的最短路径，要求所有边的权值非负。）
步骤：
初始化：创建距离数组dist用来记录源点到各顶点的最短路径长度，路径数组path用来记录最短路径中每个顶点的前驱，标记数组s用来记录已确定最短路径的顶点。
初始条件：设源点到自身的距离为 0，其他顶点的距离先初始化为无穷大。
迭代过程：每次从未确定最短路径的顶点中选择距离最小的顶点，并将其标记为已确定，然后更新其所有邻接顶点的距离值。
终止条件：所有顶点的最短路径都被确定或者无法继续更新。
最终代码如下：
void Dijkstra(MGraph g, int v) {int n = g.n;int dist[MAXV], path[MAXV], s[MAXV];int min, i, j, u;// 初始化for (i = 0; i < n; i++) {dist[i] = g.edges[v][i];s[i] = 0;if(g.edges[v][i] < INF){path[i] = v;}else{path[i] = -1;}}s[v] = 1;path[v] = -1;// 进行n-1次选择for (i = 0; i < n - 1; i++) {min = INF;u = -1;for (j = 0; j < n; j++) {if (s[j] == 0 && dist[j] < min) {u = j;min = dist[j];}}if (u == -1) break;s[u] = 1;// 更新距离和路径for (j = 0; j < n; j++) {if (s[j] == 0 && g.edges[u][j] < INF && dist[u] + g.edges[u][j] < dist[j]) {dist[j] = dist[u] + g.edges[u][j];path[j] = u;}}}Dispath(dist, path, s, n, v);
}