Dijkstra和Foloyd算法代码实现
求任意两点的最短路
一、 Dijkstra算法（求单源最短路）
很抱歉，这里没有原理讲解，只有代码（呜呜呜）：
//关于Dijkstra算法的实现，(离散刘任任第二版）例题：离散数学：P74 例题三，P78T30，
//求单源最短路
#include<stdio.h>
#include<string.h>
#define m 123456789 //表示无穷大
int v,e,k,cnt;//记录点和边的个数
bool vis[50];
//访问数组，即算法中的S集合，判断顶点是否已经被选取
int d[50];
//距离数组，即算法中的D数组,记录当前u1到点的最短通路
int c[50][50];
//算法中的C矩阵,代表两点之间的距离
int P[50];
//记录最短路径
void init(){
cnt=0;
memset(vis,0,sizeof(vis)); //将访问数组清零
memset(c,m,sizeof(c));
memset(d,m,sizeof(d));
}
void input(){
printf("请输入节点数量:\n");
scanf("%d",&v);
printf("请输入边的数量:\n");
scanf("%d",&e);
printf("输入你想要计算的点:\n");
scanf("%d",&k);
printf("输入所有的邻接的两个点和他们的边:\n");
int n=e;
while(n--){
int a,b,l;
scanf("%d %d %d",&a,&b,&l);
c[a][b] = l;
c[b][a] = l;
if(a == k) P[b] = a;
if(b == k) P[a] = b;
}
}//读入所有数据
void cal(int s){//Dijkstra算法的主要迭代流程，自行感悟
if(cnt>v) return ;
int tem=0,mins=m;
if(cnt==0){
for(int i = 1;i <= v;i++)
if(i!=s) d[i] = c[k][i];
vis[s] = 1;
cnt++;
for(int i = 1;i <= v;i++)
if(!vis[i]&&d[i] < mins) mins = d[i],tem = i;
cal(tem);
}
for(int i = 1;i <= v;i++)
if(!vis[i]&&d[i]>d[s]+c[s][i]){
d[i]=d[s]+c[s][i];
P[i]=s;
}
vis[s] = 1;
cnt++;
for(int i = 1;i <= v;i++)
if(!vis[i]&&d[i]<mins) tem = i,mins = d[i];
cal(tem);
}
void output(){//输出
for(int i = 1;i <= v;i++)
if(i!=k){
int tem=i,s[50],q=0;
printf("\n点%d到%d的最短路:%d->",k,i,k);
while(P[tem] != k){
s[q]=P[tem];
q++;
tem=P[tem];
}
for(int j=q-1;j>=0;j--) printf("%d->",s[j]);
printf("%d: %d\n",i,d[i]);
}
}
int main(){
while(1){
init();
input();
cal(k);
output();
return 0；
}
样例数据
样例一：
样例二：
样例一
5
7
1
1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
3 4 20
4 5 6
//样例二：
11
22
1
1 2 2
1 3 8
1 4 1
2 3 6
2 5 1
3 4 7
3 5 5
3 6 1
3 7 2
4 7 9
5 6 3
5 8 2
5 9 9
6 7 4
6 9 6
7 10 1
7 9 3
8 9 7
8 11 9
9 10 1
9 11 2
10 11 4
Foloyd算法实现，求任意两点的最短通路
//Foloyd 算法实现 (离散刘任任第二版）P79 T31 样例数据在最后的注释
//求任意两点的最短路
#include<stdio.h>
#include<string.h>
#define N 1000000000
int A[50][50];
int P[50][50];
int v,e;
void init(){
for(int i = 0 ;i < 50;i++)
for(int j = 0;j < 50;j++){
if(i == j) A[i][j] = 0;
else A[i][j] = N;
}
printf("顶点个数:\n");
scanf("%d",&v);
printf("边的条数:\n");
scanf("%d",&e);
}//初始化A数组 读入点的个数和边的个数
void input(int n){
printf("输入所有的邻接的两个点和他们的边:\n");
while(n--){
int a,b,l;
scanf("%d %d %d",&a,&b,&l);
A[a][b] = l;
A[b][a] = l;
}
}//读入所有数据
void cal(int k){
if(k>v) return;
for(int i = 1;i <= v;i++){
for(int j = 1; j <= v; j++){
if(A[i][j] > A[i][k] + A[k][j]){
P[i][j] = k;
A[i][j] = A[i][k] + A[k][j];
}
}
}
cal(++k);
}//迭代过程
void output(){//输出过程
printf("\n你想要计算的两点之间的最短通路：");
while(1){
int m,n;
scanf("%d %d",&n,&m);
int tem=A[n][m];
printf("%d到%d的最短通路是：",n,m);
while(P[m][n] != 0){
printf("%d->",n);
n = P[m][n];
}
printf("%d->%d：%d\n",n,m,tem);
printf("继续算下去请输入‘1’或按任意键退出：");
int s;
scanf("%d",&s);
if(s!=1) break;
}
}
int main(){
memset(P,0,sizeof(P));
init();
input(e);
cal(0);
output();
return 0;
}
测试样例
6
9
1 2 1
1 4 2
2 3 3
2 4 4
3 4 1
3 5 5
3 6 2
4 5 3
5 6 2