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