迪杰斯特拉算法
從某個頂點到其余各頂點的最短路徑（? 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的數(shù)，默認(rèn)是0
? ? for(int i=0;i<m;i++){
? ? ? ? d[i]=0;
? ? }
? ? //要想得到其他最短路徑瘩蚪，需要循環(huán)m-1次泉懦，每次確定一個最短路徑
? ? int k=m-1;
? ? int v[m];//看是否已經(jīng)確定是最短路徑了，初始化為0如果是1標(biāo)識確定了
? ? 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的元素標(biāo)識為最小的
? ? ? ? ? ? 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;//標(biāo)識確定了最短路徑的下標(biāo)
? ? 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的最小下標(biāo)并且v[i]==0的下標(biāo)
? ? ? ? for(int i=0;i<m;i++){
? ? ? ? ? ? if(d[i]!=0&&b&&v[i]==0){//找到第一個非0的元素標(biāo)識為最小的
? ? ? ? ? ? ? ? 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;
}
結(jié)果：
弗洛伊德算法
各個頂點之間的最短距離
舉例：
有一個帶權(quán)有向圖言沐，用弗洛伊德算法求各頂點間的最短距離的矩陣序列A1,A2,A3
每一對頂點之間的路徑邓嘹，初始用A（-1）標(biāo)識：
求A(0),A(1),A(2),
A(0)在A(-1)的基礎(chǔ)上求A[i][0]+A[0][j]<A[i][j]
比較好使不易出錯的方法：先找出第0列的元素，然后找出第0行的元素险胰，然后加起來汹押，構(gòu)造一個新的矩陣，這個矩陣和A（-1）矩陣比較起便，找出其中比A（-1）矩陣中的元素小的棚贾，然后代替A(-1)中的元素，就是A（0）矩陣了
A（1）在A（0）的基礎(chǔ)上
A（2）在A（1）的基礎(chǔ)上
代碼：
#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];//臨時數(shù)組
? ? ? ? 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數(shù)組："<<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數(shù)組"<<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;
}
結(jié)果：
