正确认识部门网站建设,要找做冲压件的厂去哪个网站找,软件介绍网站源码,企业网站建基本思想是#xff1a; 假设求从顶点vi到vj的最短路径。 如果从vi到vj有弧#xff0c;则从vi到vj存在一条长度为arcs[i][j]的路径#xff0c;该路径不一定是最短路径#xff0c;尚需进行n次试探。 首先考虑路径#xff08;vi, v0, vj#xff09;是否存在#xff08;判别…基本思想是 假设求从顶点vi到vj的最短路径。 如果从vi到vj有弧则从vi到vj存在一条长度为arcs[i][j]的路径该路径不一定是最短路径尚需进行n次试探。 首先考虑路径vi, v0, vj是否存在判别弧vi, v0和v0, vj是否存在。 如果存在则比较vi, vj和vi, v0, vj的路径长度取长度较短者为从vi到vj的中间顶点的序号不大于0的最短路径。 假如在路径上再增加一个顶点v1也就是说如果vi, …, v1和v1, …, vj分别是当前找到的中间顶点的序号不大于0的最短路径那么vi, …, v1, … , vj就有可能是从vi到vj的中间顶点的序号不大于1的最短路径。 将它和已经得到的从vi到vj中间顶点序号不大于0的最短路径相比较从中选出中间顶点的序号不大于1的最短路径之后再增加一个顶点v2继续进行试探依此类推。 在一般情况下若vi, …, vk和vk, …, vj分别是从vi到vk和从vk到vj的中间顶点的序号不大于k-1的最短路径则将vi, …, vk, …, vj和已经得到的从vi到vj且中间顶点序号不大于k-1的最短路径相比较其长度较短者便是从vi到vj的中间顶点的序号不大于k的最短路径。 这样在经过n次比较后最后求得的必是从vi到vj的最短路径。 按此方法可以同时求得各对顶点间的最短路径。
求任意两顶点间的最短路径Floyd算法如下:
#include iostream
using namespace std;const int MAXW 30000;
const int MaxVertexNum 30;
typedef char VertexType;
class MGraph
{
public:void CreateGraph();void ShortestPath_Floyd();void Print_Path_Floyd(int v,int w);private:int vertexnum;VertexType vertexs[MaxVertexNum];int edgenum;bool P[MaxVertexNum][MaxVertexNum][MaxVertexNum];int D[MaxVertexNum][MaxVertexNum];int arcs[MaxVertexNum][MaxVertexNum];
};void MGraph::CreateGraph()
{cout 请输入节点数和边条数 endl;cin vertexnum edgenum;for (int i 0; i vertexnum; i)for (int j 0; j vertexnum; j)arcs[i][j] MAXW;cout 请依次输入按序号0到n顶点的中存储的信息 endl;for (int i 0; i vertexnum; i){cin vertexs[i];}cout 下面输入边的信息 endl;for (int i 0; i edgenum; i){int v1, v2, w;cout 输入边i,j对应的顶点序号i,j,然后再输入该边的权值 endl;cin v1 v2 w;arcs[v1][v2] w;}
}void MGraph::ShortestPath_Floyd()
{//用Floyd算法求有向图G中各对顶点v和w之间的最短路径P[v][w]及其带权长度D[v][w]//若P[v][w][u] 1则u是从v到w当前求得的最短路径上的顶点for (int v 0;vvertexnum;v)for (int w 0; w vertexnum; w){D[v][w] arcs[v][w];for (int u 0; u vertexnum; u) P[v][w][u] 0;if (D[v][w] MAXW)//从v到w有直接路径{P[v][w][v] 1;P[v][w][w] 1;}}for (int u 0;u vertexnum;u)for (int v 0;vvertexnum;v)for (int w 0; w vertexnum; w){if (D[v][u] D[u][w] D[v][w]){D[v][w] D[v][u] D[u][w];P[v][w][u] 1;}}
}void MGraph::Print_Path_Floyd(int v, int w)
{int i;for (i 0; i vertexnum; i)if (i ! v i ! w P[v][w][i] true) break;if (i vertexnum) cout v - w endl;else{Print_Path_Floyd(v, i);Print_Path_Floyd(i, w);}
}int main()
{MGraph g;g.CreateGraph();g.ShortestPath_Floyd();int v, w;cin v w;g.Print_Path_Floyd(v, w);return 0;
}
