最短路径：
在一个带权图中，顶点V0到图中任意一个顶点Vi的一条路径所经过边上的权值之和，定义为该路径的带权路径长度，把带权路径最短的那条路径称为最短路径。
DiskStra算法：
求单源最短路径，即求一个顶点到任意顶点的最短路径，其时间复杂度为O(V*V)
如图所示：求顶点0到各顶点之间的最短路径
代码实现：
#include<stdio.h>#include<stdlib.h>#define MaxVexNum 50#define MaxInt 32767#define MaxEdgeNum 50//邻接矩阵typedef int VertexType;typedef int EdgeType;typedef struct AMGraph{VertexType vexs[MaxVexNum];//顶点表 EdgeType arcs[MaxVexNum][MaxVexNum];//邻接矩阵表 int vexnum,edgenum;//顶点数，边数 }AMGraph; void createGraph(AMGraph &g){//创建无向图 printf("请输入顶点数：");scanf("%d",&g.vexnum);printf("\n请输入边数：");scanf("%d",&g.edgenum);//初始化顶点表 for(int i=0;i<g.vexnum;i++){g.vexs[i]=i; } for(int i=0;i<g.vexnum;i++){for(int j=0;j<g.vexnum;j++){g.arcs[i][j]=MaxInt;if(i==j) g.arcs[i][j]=0;}} printf("请输入边的信息以及边的权值(顶点是0~n-1)\n");for(int i=0;i<g.edgenum;i++){int x,y,w;scanf("%d%d%d",&x,&y,&w);g.arcs[x][y]=w;//g.arcs[y][x]=w;}}void PrintGraph(AMGraph g){printf("邻接矩阵为:\n");for(int i=0;i<g.vexnum;i++) {printf(" %d",g.vexs[i]);}printf("\n");for(int i=0;i<g.vexnum;i++){printf("%d ",g.vexs[i]);for(int j=0;j<g.vexnum;j++){if(g.arcs[i][j]==32767){printf("∞ "); }else{printf("%d ",g.arcs[i][j]);}}printf("\n");} }//Dijkstra算法，求单源最短路径void Dijkstra(AMGraph g,int dist[],int path[],int v0){int n=g.vexnum,v;int set[n];//set数组用于记录该顶点是否归并 //第一步：初始化 for(int i=0;i<n;i++){set[i]=0;dist[i]=g.arcs[v0][i];if(dist[i]<MaxInt){//若距离小于MaxInt说明两点之间有路可通 path[i]=v0;//则更新路径i的前驱为v }else{path[i]=-1; //表示这两点之间没有边} }set[v0]=1;//将初始顶点并入 path[v0]=-1;//初始顶点没有前驱//第二步 for(int i=1;i<n;i++){//共n-1个顶点 int min=MaxInt;//第二步：从i=1开始依次选一个距离顶点的最近顶点 for(int j=0;j<n;j++){if(set[j]==0&&dist[j]<min){v=j;min=dist[j];}}//将顶点并入 set[v]=1;//第三步：在将新结点并入后，其初始顶点v0到各顶点的距离将会发生变化，所以需要更新dist[]数组for(int j=0;j<n;j++){if(set[j]==0&&dist[v]+g.arcs[v][j]<dist[j]){dist[j]=dist[v]+g.arcs[v][j];path[j]=v;}} } //输出 printf(" ");for(int i=0;i<n;i++) printf("%d ",i);printf("\ndist[]:");for(int i=0;i<n;i++) printf("%d ",dist[i]);printf("\npath[]:");for(int i=0;i<n;i++) printf("%d ",path[i]);}int main(){AMGraph g;createGraph(g);int dist[g.vexnum];int path[g.vexnum];Dijkstra(g,dist,path,0);}
Floyd算法：
求各顶点之间的最短路径,其时间复杂度为O(V*V*V)
如图所示，求<1,0>之间的最短路径：
代码实现：
#include<stdio.h>#include<stdlib.h>#define MaxVexNum 50#define MaxInt 32767#define MaxEdgeNum 50//邻接矩阵typedef int VertexType;typedef int EdgeType;typedef struct AMGraph{VertexType vexs[MaxVexNum];//顶点表 EdgeType arcs[MaxVexNum][MaxVexNum];//邻接矩阵表 int vexnum,edgenum;//顶点数，边数 }AMGraph; void createGraph(AMGraph &g){//创建无向图 printf("请输入顶点数：");scanf("%d",&g.vexnum);printf("\n请输入边数：");scanf("%d",&g.edgenum);//初始化顶点表 for(int i=0;i<g.vexnum;i++){g.vexs[i]=i; } for(int i=0;i<g.vexnum;i++){for(int j=0;j<g.vexnum;j++){g.arcs[i][j]=MaxInt;if(i==j) g.arcs[i][j]=0;}} printf("请输入边的信息以及边的权值(顶点是0~n-1)\n");for(int i=0;i<g.edgenum;i++){int x,y,w;scanf("%d%d%d",&x,&y,&w);g.arcs[x][y]=w;//g.arcs[y][x]=w;}}void PrintGraph(AMGraph g){printf("邻接矩阵为:\n");for(int i=0;i<g.vexnum;i++) {printf(" %d",g.vexs[i]);}printf("\n");for(int i=0;i<g.vexnum;i++){printf("%d ",g.vexs[i]);for(int j=0;j<g.vexnum;j++){if(g.arcs[i][j]==32767){printf("∞ "); }else{printf("%d ",g.arcs[i][j]);}}printf("\n");} }//Floyd算法//递归输出两个顶点直接最短路径 void printPath(int u,int v,int path[][MaxVexNum]){if(path[u][v]==-1){printf("[%d %d] ",u,v);}else{int mid=path[u][v];printPath(u,mid,path);printPath(mid,v,path);}}void Floyd(AMGraph g,int path[][MaxVexNum]){int n=g.vexnum;int A[n][n];//第一步：初始化path[][]和A[][]数组 for(int i=0;i<n;i++){for(int j=0;j<n;j++){A[i][j]=g.arcs[i][j];path[i][j]=-1; }}//第二步：三重循环，寻找最短路径 for(int v=0;v<n;v++){//第一层是代表中间结点 for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(A[i][j]>A[i][v]+A[v][j]){A[i][j]=A[i][v]+A[v][j];path[i][j]=v;}}} } } int main(){AMGraph g;createGraph(g);PrintGraph(g);int path[MaxVexNum][MaxVexNum];Floyd(g,path);printPath(1,0,path);}
代码运行截图：
