2.Path[i]：记录源点到i点当前最短路径上i点的直接前驱顶点序号，相当于Prim的数组 。【路是一步步走的，记它的上一步就好，上一步还记得上上步 。】
3.D[i]：记录源点到i点的当前最短路径长度，相当于Prim的数组 。
代码
#pragma region Dijkstratypedef int Patharc[MAXVEX];/* 用于存储最短路径下标的数组 */typedef int ShortPathTable[MAXVEX];/* 用于存储到各点最短路径的权值和 *//*Dijkstra算法，求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v] *//*P[v]的值为前驱顶点下标,D[v]表示v0到v的最短路径长度和 */void ShortestPath_Dijkstra(MGraph G, int v0, Patharc &P, ShortPathTable &D) {int v, w, k, min;int final[MAXVEX];/* final[w]=1表示求得顶点v0至vw的最短路径 */for (v = 0; v < G.numVertexes; v++)/* 初始化数据 */{final[v] = 0;/* 全部顶点初始化为未知最短路径状态 */D[v] = G.arc[v0][v];/* 将与v0点有连线的顶点加上权值 */P[v] = -1;/* 初始化路径数组P为-1*/}D[v0] = 0;/* v0至v0路径为0 */final[v0] = 1;/* v0至v0不需要求路径 *//* 开始主循环，每次求得v0到某个v顶点的最短路径 */for (v = 1; v < G.numVertexes; v++) {min = INFINITY;/* 当前所知离v0顶点的最近距离 */for (w = 0; w < G.numVertexes; w++) /* 寻找离v0最近的顶点 */{if (!final[w] && D[w] < min) {k = w;min = D[w];/* w顶点离v0顶点更近 */}}final[k] = 1;/* 将目前找到的最近的顶点置为1 */for (w = 0; w < G.numVertexes; w++) /* 修正当前最短路径及距离 */{/* 如果经过v顶点的路径比现在这条路径的长度短的话 */if (!final[w] && (min + G.arc[k][w] < D[w])) { /*说明找到了更短的路径，修改D[w]和P[w] */D[w] = min + G.arc[k][w];/* 修改当前路径长度 */P[w] = k;}}}}#pragma endregion
同样是三个部分 。初始化+大循环内子循环1+大循环内子循环2
零：final[v] = 0; D[v] = G.arc[v0][v];P[v] = -1;
一：min = D[w]; k = w;
二：P[w] = k; D[w] = min + G.arc[k][w];
求单源点到其他点，时间复杂度O(n2) 。如果求图中任意两点，每个点来一次，存起来 。O(n3)
完整的求最短路径代码
from大话数据结构
#include "stdio.h"#include "stdlib.h"#include "io.h"#include "math.h"#include "time.h"#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXEDGE 20#define MAXVEX 20#define INFINITY 65535typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ typedef struct{int vexs[MAXVEX];int arc[MAXVEX][MAXVEX];int numVertexes, numEdges;}MGraph;typedef int Patharc[MAXVEX];/* 用于存储最短路径下标的数组 */typedef int ShortPathTable[MAXVEX];/* 用于存储到各点最短路径的权值和 *//* 构件图 */void CreateMGraph(MGraph *G){int i, j;/* printf("请输入边数和顶点数:"); */G->numEdges=16;G->numVertexes=9;for (i = 0; i < G->numVertexes; i++)/* 初始化图 */{G->vexs[i]=i;}for (i = 0; i < G->numVertexes; i++)/* 初始化图 */{for ( j = 0; j < G->numVertexes; j++){if (i==j)G->arc[i][j]=0;elseG->arc[i][j] = G->arc[j][i] = INFINITY;}}G->arc[0][1]=1;G->arc[0][2]=5; G->arc[1][2]=3; G->arc[1][3]=7; G->arc[1][4]=5; G->arc[2][4]=1; G->arc[2][5]=7; G->arc[3][4]=2; G->arc[3][6]=3; G->arc[4][5]=3;G->arc[4][6]=6;G->arc[4][7]=9; G->arc[5][7]=5; G->arc[6][7]=2; G->arc[6][8]=7;G->arc[7][8]=4;for(i = 0; i < G->numVertexes; i++){for(j = i; j < G->numVertexes; j++){G->arc[j][i] =G->arc[i][j];}}}/*Dijkstra算法，求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v] *//*P[v]的值为前驱顶点下标,D[v]表示v0到v的最短路径长度和 */void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D){int v,w,k,min;int final[MAXVEX];/* final[w]=1表示求得顶点v0至vw的最短路径 */for(v=0; v