一、单源：Dijkstra
/* Dijkstra 思想：从源点开始，每次选择一个距源点距离最小的点加入集合，更新该点的邻接顶点的距离，直到所有的顶点都加入进来。 步骤： 初始化：dist为0或者MAX,p为边长 进行n-1次更新：找出dist最小的点，判断邻接顶点距离是否能更新*/ #include<iostream> using namespace std; #define MAX 100000 #define N 100void Dijkstra(int **p,int s,int n,int* dist,int *path) {int visit[N]={0};//都未确定距离 int i,j;for(i=0;i<n;i++){dist[i]=p[s][i];path[i]=-1;}for(i=1;i<n;i++){//找距离最小的点int min_value=MAX,min;for(j=0;j<n;j++)if(min_value>dist[j] && !visit[j])min=j,min_value=dist[j];visit[min]=1;//更新邻接点for(int j=0;j<n;j++)if(!visit[j] && dist[j]>dist[min]+p[min][j]){path[j]=min;dist[j]=dist[min]+p[min][j];}} } void print(int * d,int n,int *path) {for(int i=0;i<n;i++){cout<<i<<':'<<d[i]<<"---"<<i<<' ';int j=i;while(path[j]!=-1){cout<<path[j]<<' ';j=path[j];}cout<<endl;} }int main() {int n=6;int i,j;int **p=new int*[n];int *dist=new int[n];int *path=new int[n];for(i=0;i<n;i++){p[i]=new int[n];for(j=0;j<n;j++){p[i][j]=(i==j?0:MAX);}}//赋值p[0][1]=10;p[0][3]=30;p[1][2]=50;p[1][4]=100;p[2][4]=5;p[3][2]=20;p[3][4]=60;p[4][5]=10;//调用Dijkstra(p,0,n,dist,path);print(dist,n,path);return 0; }
二、多源：Floyd
for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(e[i][j]>e[i][k]+e[k][j])e[i][j]=e[i][k]+e[k][j];