迪杰斯特拉算法时间复杂度为O(n^2)，其中n为顶点个数。
该算法用于求单源最短路径。并且图中的边不允许带负权值。
#include <iostream>using namespace std;#define Maxsize 100typedef char VertexType;typedef int EdgeType;typedef struct{VertexType Vex[Maxsize];EdgeType edge[Maxsize][Maxsize];int vexnum,arcnum;}MGraph;void Dijkstra(MGraph G,int v,int dist[],int path[]){int set[Maxsize];int min,i,j,u;for(i=0;i<G.vexnum;i++){//初始化 dist[i]=G.edge[v][i];set[i]=0;if(G.edge[v][i]<INF)//两顶点无边path[i]=v;elsepath[i]=-1; }set[v]=1;path[v]=-1;for(i=1;i<=G.vexnum;i++){min=INF;for(j=0;j<G.vexnum;j++){if(set[j]==0&&dist[j]<min){//未加入源S且距离小于min u=j;min=dist[j];}set[u]=1;//将选出的顶点并入最短路径中for(j=0;j<G.vexnum;j++){//更新源S与剩余顶点距离 if(set[j]==0&&dist[u]+G.edge[u][j]<dist[j]){dist[j]=dist[u]+G.edge[u][j];path[j]=u;}} }}}
