Floyd-Warshall
就是求所有顶点对的最短路径长度#include <iostream>#include <vector>using namespace std;typedef struct{int vexs;int edges;int n;int e;}MGraph;#define INFINITE 2048void CreateGraphM(MGraph *G){int N1,N2;cout<<"Enter the number of vertexs and edges: "<<endl;cin>>(G->n)>>(G->e);for(int i=0;i<G->n;i++) cin>>(G->vexs);for(int i=0;i<G->n;i++) for(int j=0;j<G->n;j++) G->edges=-1; cout<<"EDGES: "<<endl;for(int k=0;k<G->e;k++){ int weight; cin>>N1>>N2>>weight; G->edges=weight;}return;}vector< vector<int> > Floyed_Warshall(MGraph *G){ vector< vector<int> > Dist(G->n,vector<int>(G->n)); for(int i=0;i<G->n;i++) for(int j=0;j<G->n;j++) Dist = G->edges;for(int i=0;i<G->n;i++) Dist = 0;for(int i=0;i<G->n;i++) for(int j=0;i<G->n;i++) for(int k=0;i<G->n;i++) if(Dist + Dist < Dist && \ Dist != -1 && \ Dist != -1) Dist = Dist + Dist;return Dist;}int main(){vector< vector<int> > Dist;MGraph *G = new MGraph;CreateGraphM(G);Dist = Floyed_Warshall(G);cout<<endl;for(int i=0;i<G->n;i++) for(int j=0;j<G->n;j++) if(Dist!=-1 && i!=j) cout<<i+1<<" "<<j+1<<" "<<Dist<<endl; cout<<endl;delete G;return 0;}
页:
[1]