迪杰斯特拉算法
从某个顶点到其余各顶点的最短路径（ o（n的平方））
举个例子：
问题：求出下图中顶点1到其余各顶点的最短路径
这个图的计算方法，
比如s是1的时候，DIST就是1到各个顶点的最短距离，不能到达就是无穷，可以确定最短的是1->5
然后，s就是1,5,DIST就是从5到其他顶点的距离+上图1->5的距离，和1时候的DIST对比，比他小填入就可以了，否则填上面的
...其他类似
从图中可以看出顶点1到其他顶点的最短路径依次是20,31,28,10,17,25,35,按迪杰斯特拉算法所选顶点依次是5,6,2,7,4,3,8
代码：
#include <iostream>
using namespace std;
int main(){
int m,n;//m是有多少个顶点，n是从哪个顶点开始
cin>>m>>n;
int p[m][m];
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
cin>>p[i][j];
}
}
int d[m];//用来存储n顶点到其他顶点的最短路径，输出从1到m-1的数，默认是0
for(int i=0;i<m;i++){
d[i]=0;
}
//要想得到其他最短路径，需要循环m-1次，每次确定一个最短路径
int k=m-1;
int v[m];//看是否已经确定是最短路径了，初始化为0如果是1标识确定了
for(int i=0;i<m;i++){
v[i]=0;
}
int p1=n;
int min;
int min_i;
bool b=true;
for(int i=0;i<m;i++){
if(i==n){
continue;
}
if(p[n][i]!=0&&b){//找到第一个非0的元素标识为最小的
min=p[n][i];
min_i=i;
b=false;
d[i]=p[n][i];
}
if(!b&&p[n][i]!=0){
if(p[n][i]<min){
min=p[n][i];
min_i=i;
}
d[i]=p[n][i];
}
}
v[min_i]=1;//标识确定了最短路径的下标
n=min_i;//有最小的从最小的那个开始，和上一次的d[i]对比，看是否有比他小的
k=k-1;
for(int i=0;i<m;i++){
cout<<d[i]<<" ";
}
cout<<n<<endl;
while(k--){//进行m-1次遍历，确定最小
for(int i=0;i<m;i++){
if(v[i]==1||i==p1){
continue;
}
if(p[n][i]!=0&&d[i]!=0){
if(p[n][i]+d[min_i]<d[i]){
d[i]=p[n][i]+d[min_i];
}
}
if(p[n][i]!=0&&d[i]==0){
d[i]=p[n][i]+d[min_i];
}
}
b=true;
//确定d[i]不为0的最小下标并且v[i]==0的下标
for(int i=0;i<m;i++){
if(d[i]!=0&&b&&v[i]==0){//找到第一个非0的元素标识为最小的
min=d[i];
min_i=i;
b=false;
}
if(!b&&d[i]!=0&&v[i]==0){
if(d[i]<min){
min=d[i];
min_i=i;
}
}
}
v[min_i]=1;
n=min_i;
for(int i=0;i<m;i++){
cout<<d[i]<<" ";
}
cout<<n<<endl;
}
for(int i=0;i<m;i++){
if(i!=p1){
if(d[i]==0){
cout<<-1<<" ";
}else{
cout<<d[i]<<" ";
}
}
}
return 0;
}
结果：
弗洛伊德算法
各个顶点之间的最短距离
举例：
有一个带权有向图，用弗洛伊德算法求各顶点间的最短距离的矩阵序列A1,A2,A3
每一对顶点之间的路径，初始用A（-1）标识：
求A(0),A(1),A(2),
A(0)在A(-1)的基础上求A[i][0]+A[0][j]<A[i][j]
比较好使不易出错的方法：先找出第0列的元素，然后找出第0行的元素，然后加起来，构造一个新的矩阵，这个矩阵和A（-1）矩阵比较，找出其中比A（-1）矩阵中的元素小的，然后代替A(-1)中的元素，就是A（0）矩阵了
A（1）在A（0）的基础上
A（2）在A（1）的基础上
代码：
#include <iostream>
using namespace std;
int main(){
int n;
cin>>n;
int p[n][n];
int v[n][n];//=1就是无穷
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>p[i][j];
if(p[i][j]==0&&i!=j){
v[i][j]=1;
}else{
v[i][j]=0;
}
}
}
int m=n;
int k=0;
while(m--){
int temp[n][n];//临时数组
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(v[k][j]==1||i==j||v[i][k]==1){//如果是无穷,或者是对角线上的值
temp[i][j]=p[i][j];
}else{
temp[i][j]=p[k][j]+p[i][k];
}
}
}
k++;
// cout<<"temp数组："<<endl;
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// cout<<temp[i][j]<<" ";
// }
// cout<<endl;
// }
// cout<<endl;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j){
continue;
}else{
if(v[i][j]==1){//是无穷
p[i][j]=temp[i][j];
if(p[i][j]!=0){
v[i][j]=0;
}
}else{//不是无穷
if(temp[i][j]<p[i][j]){
p[i][j]=temp[i][j];
}
}
}
}
}
// cout<<" p数组"<<endl;
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// cout<<p[i][j]<<" ";
// }
// cout<<endl;
// }
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j){
cout<<p[i][j]<<" ";
continue;
}else if(p[i][j]==0){
p[i][j]=-1;
}
cout<<p[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
结果：
