在带权值的有向图中，由源点到终点权值和最小的路径被称为最短路径。 （路径上第一个顶点为源点，最后一个点为终点）
迪杰斯特拉算法 概述迪杰斯特拉算法解决的是给定带权有向图G和源点V0,求从V0到G中其余顶点的最短路径， 该算法是一个按路径长度递增的次序产生最短路径的算法。
算法思想设G=(V,E)为一个带全有向图，把图中顶点集合V分成两组。第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将所到达最短路径的顶点加入到集合S中，直到全部顶点都加入到S中）。第二组为其余未确定最短路径的顶点集合（用U表示，U=V-S，U中的顶点不断的加入到S中，直到U为空，S=V）。在U加入S的过程中，始终保持源点到S中各顶点的最短路径长度小于或等于源点到U中任意顶点的最短路径长度。
算法实现 存储结构使用带权的邻接矩阵arcs来表示带权有向网G
辅助数组一维数组S[i]：记录从源点V0到终点Vi是否已经被确定最短路径长度，true表示确定，false表示尚未被确定 一维数组Path[i]：记录从源点V0到终点Vi的当前最短路径上Vi的直接前驱顶点序号。其初值为：如果从V0到Vi有弧，则Path[i]为V0，否则为-1 一维数组D[i]：记录从源点V0到终点Vi的当前最短路径长度。其初值为：如果从V0到Vi有弧，则D[i]为弧上的权值，否则为MaxInt
//-----------图的邻接矩阵存储表示---------#define MaxInt 32767#define MVNum 100typedef string VerTexType;typedef int ArcType;typedef struct{VerTexType vex[MVNum];ArcType arcs[MVNum][MVNum];int vexnum, arcnum;}AMgraph;bool S[MVNum];//辅助数组，标记顶点是否已经确定最短路径int Path[MVNum];//辅助数组，记录从源点V0到终点vi的当前最短路径上的直接前驱顶点序号//最短路径上的直接前驱顶点序号，如果从V0到vi有弧，则Path[i]为v0，否则为-1int D[MVNum];//记录最小路径的值 代码实现 void ShortestPath_DIJ(AMgraph G, int v0,int end){//用Dijkstra算法求有向网的v0顶点到其余顶点的最短路径，并输出从源点v0到终点end的路径int n = G.vexnum;//n为G中顶点的个数int v;for (v = 0; v
