最短路径详细解析(Dijkstra+Floyd)

最短路径是非常重要的算法，其中Floyd算法代码比较简单，但是时间复杂高；而Dijkstra算法比较快，然而比较复杂。
下面则通过实例更加理解其中的算法。

• Dijkstra
• Folyd

因为Dijsktra比较复杂，这里给出一些解释。分别引入了dist[],path[],set[],解释在图下。

本次算法以下图为例，其中上图已给出dist，path,set数组的正确值。

话不多说，直接放代码。

#include 

#define INFINITY 65525
using namespace std;

typedef struct{
    char vexs[100];
    int arc[100][100];
    int numVer,numEdges;
}MGraph;

void Creat(MGraph &g){
    int i,j,k,w;
    cout<<"输入顶点数和边数"<>g.numVer>>g.numEdges;
    for(i=0;i>g.vexs[i];
    }
    for(i=0;i>i>>j>>w;
        g.arc[i][j]=w;
    }
}

int path[500];
int dist[500];
int set[500];

void Dijkstra(MGraph g,int v){
    int min,i,j,u;
    
    for(i=0;i 
下面是运行结果，可知与上图dist[]数组一致。
 
 
Folyd 
因为Folyd比较简单，故不再进行解释，直接放图演示。
 核心算法
 
				if(A[i][j]>A[i][k]+A[k][j]){
                    A[i][j]=A[i][k]+A[k][j];
                    Path[i][j]=k;
                }
 

 代码
 
#include 

#define INFINITY 65525
using namespace std;

typedef struct{
    char vexs[100];
    int arc[100][100];
    int numVer,numEdges;
}MGraph;

void Creat(MGraph &g){
    int i,j,k,w;
    cout<<"输入顶点数和边数"<>g.numVer>>g.numEdges;
    for(i=0;i>g.vexs[i];
    }
    for(i=0;i>i>>j>>w;
        g.arc[i][j]=w;
    }
}

int A[500][500];
int Path[500][500];

void Folyd(MGraph g){
    int i,j,k;
    for(i=0;iA[i][k]+A[k][j]){
                    A[i][j]=A[i][k]+A[k][j];
                    Path[i][j]=k;
                }
            }
        }
    }
}

int main(){
    MGraph g;
    Creat(g);
    Folyd(g);
    cout<<"最短路径矩阵图"<运行结果图
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5610727.html