复习：最短路径

一、基本概念

• 最短路径：在非网图中，最短路径是指两顶点之间经历的边数最少的路径；在网图中，最短路径是指两顶点之间经历的边上权值之和最少的路径。
• 源点：路径上的第一个顶点。
• 终点：路径上最后一个顶点。

二、Dijkstra算法（只适用于简单路径，不适合回路）
Dijkstra算法用于求单元点最短路径问题，给定有向网图G=(V,E)和源点v属于V，求v到G中其余各个顶点的最短路径。
①基本思路：

1. 将顶点集合V分成两个集合，集合S存放源点v和已经确定最短路径的顶点，另一个集合V-S存放未确定最短路径的顶点。
2. 初始化：S只包含源点v，对vi属于V-S，待定路径表为从源点v到vi的有向边。
3. 在待定路径表中找到当前最短路径，v…vk，将vk加入S，对vi属于V-S，将路v…vkvi与待定路径表中从源点v到vi的最短路径相比较，去路径长度较小者为当前最短路径。

②存储结构：

1. 图的存储结构：邻接矩阵
2. 辅助数组dist[n]：元素dist[i]表示当前所找到的从源头v到终点vi的最短路径的长度。(dist[i] = min{dist[i]，dist[k]+edge[k][i])
3. 辅助数组path[n]：元素path[i]是一个字符串，表示当前从源点v到终点vi的最短路径。（没有弧则为空串）

void Dijkstra(int v)//从源点v出发
{int i,k,num,dist[MaxSize];string path[MaxSize];for(i = 0 ;i<vertexNum ; i++)//初始化数组dist和path{dist[i] = edge[v][i];if(dist[i]!=100)//假设100为边上权的最大值path[i] = vertex[v]+vertex[i];//vertex数组存储的是顶点，+为字符串连接操作elsepath[i] = "";//没有边可达，即无穷，则为空串}for(num = 1 ; num<vertexNum ; num++)//扫描V-S中的所有顶点{k = Min(dist,vertexNum);//在dist数组中（路径列表）找到最小值并返回其下标（注意要越过0值）cout<<path[k]<<dist[k];for(i = 0 ; i<vertexNum ; i++)//插入新加入的k顶点，修改dist和path数组{if(dist[i]>dist[k]+edge[k][i]){dist[i] = dist[k]+edge[k][i];path[i] = path[k]+vertex[i];//+为字符串连接操作}}dist[k] = 0;//将顶点k加入到集合S中}
}

Dijkstra算法的时间复杂度为O(n^2)，有两个规律：

1. 最短路径是按路长度递增的次序产生的。
2. 最短路径上可能经过已产生终点的顶点。

实例：以邻接矩阵为存储结构，实现有向带权图的最短路径算法Dijkstra，完整代码如下：

#include 
using namespace std;const int MaxSize = 10;           //图中最多顶点个数
int visited[MaxSize]={0};
const int MAX = 1000; struct element			//改进：使用结构体数组代替lowcast数组以及adjvex数组
{int lowcost, adjvex;
};int MinEdge(element *e,int vertexNum);template <class DataType>
class MGraph
{
public:MGraph(DataType a[ ], int n, int e);    //构造函数，建立具有n个顶点e条边的图~MGraph( ) { }                     //析构函数为空void DFSTraverse(int v);              //深度优先遍历图void BFSTraverse(int v);               //广度优先遍历图void Dijkstra(int v);
private:DataType vertex[MaxSize];          //存放图中顶点的数组int edge[MaxSize][MaxSize];          //存放图中边的数组int vertexNum, edgeNum;             //图的顶点数和边数
};template <class DataType>
MGraph<DataType>::MGraph(DataType a[ ], int n, int e)
{int i, j, k ,x;vertexNum = n;edgeNum = e;for (i = 0; i < vertexNum; i++)vertex[i] = a[i];for (i = 0; i < vertexNum; i++)for (j = 0; j < vertexNum; j++)edge[i][j] = MAX;for (k = 0; k < edgeNum; k++){cout << "请输入两个边顶点的序号：";cin >> i >> j;			//输入边依附的两个顶点的编号 cout << "请输入边的权值："; cin >> x;edge[i][j] = x;		//置边的标志为1 edge[j][i] = x;		//无向图 边是相通的 }
}template <class DataType>
void MGraph<DataType>::DFSTraverse(int v)
{cout << vertex[v];visited[v] = 1;for (int j = 0; j < vertexNum; j++){if (edge[v][j] != MAX && visited[j] == 0)DFSTraverse(j); //存在与v相连的j点且j点未被访问过 则进一步遍历j点 }
}template <class DataType>
void MGraph<DataType>::BFSTraverse(int v)
{int w, j, Q[MaxSize];int front = -1, rear = -1;cout << vertex[v];visited[v] = 1;Q[++rear] = v;		//v点入队 while (front != rear){w = Q[++front];	//Q出队值 w for (j = 0; j < vertexNum; j++)//遍历所有可能与w相连的点 若有，则输出、标记、入队 {if (edge[w][j] != MAX && visited[j] == 0)//存在与w点相连的j点且j点未被访问过 则输出j点值 然后标记j点将j点入队 {cout << vertex[j];visited[j] = 1;Q[++rear] = j;}}}
}int Min(int dist[],int vertexNum)
{int min = 100;for(int i=0 ; i<vertexNum ; i++){if(dist[i]<min)min = dist[i];}return min;} template<typename DataType>
void MGraph<DataType>::Dijkstra(int v)//从源点v出发
{int i,k,num,dist[MaxSize];string path[MaxSize];for(i = 0 ;i<vertexNum ; i++)//初始化数组dist和path{dist[i] = edge[v][i];if(dist[i]!=100)//假设100为边上权的最大值path[i] = vertex[v]+vertex[i];//vertex数组存储的是顶点，+为字符串连接操作elsepath[i] = "";//没有边可达，即无穷，则为空串}for(num = 1 ; num<vertexNum ; num++)//扫描V-S中的所有顶点{k = Min(dist,vertexNum);//在dist数组中（路径列表）找到最小值并返回其下标（注意要越过0值）cout<<path[k]<<dist[k];for(i = 0 ; i<vertexNum ; i++)//插入新加入的k顶点，修改dist和path数组{if(dist[i]>dist[k]+edge[k][i]){dist[i] = dist[k]+edge[k][i];path[i] = path[k]+vertex[i];//+为字符串连接操作}}dist[k] = 0;//将顶点k加入到集合S中}
}int main( )
{char ch[]={'A','B','C','D','E'};MGraph<char> MG(ch, 5, 7);for (int i=0; i<MaxSize; i++)visited[i]=0;cout<<"深度优先遍历序列是：";MG.DFSTraverse(0);cout<<endl;for (int i=0; i<MaxSize; i++)visited[i]=0;cout<<"广度优先遍历序列是：";MG.BFSTraverse(0);cout<<endl;cout<<"从顶点"<<ch[0]<<"到各终点的最短路径分别是："<<endl;MG.Dijkstra(0);cout<<endl;system("pause");
}

二、Floyd算法（地铁路线规划）
Floyd算法用于求每一对顶点之间的最短路径问题，给定带权有向图G=（V,E），对任意顶点vi和vj(i不等于j)，求顶点vi到vj的最短路径。
①基本思想：

1. 假设从vi到vj是最短路径，然后进行n次试探。
2. 比较vi vj和vi vk vj的路径长度，去长度较短者作为vi到vj中间顶点的编号不大于0的最短路径。

②存储结构：

1. 图的存储结构：邻接矩阵
2. 辅助数组dist[n][n]：存放在迭代过程中求得的最短路径。（dist_-1[i][j] = edge[i][j]；dist_k[i][j] = min{dist_k[i][j]，dist_k[i][k]+dist_k-1[k][j]}）->插入顶点k后更新路径的长度
3. 辅助数组path[n][n]：在迭代中存放vi到vj的最短路径，初始为“vi vj”

void Floyd()
{int i,j,k,dist[MaxSize][MaxSize];string path[MaxSize][MaxSize];for(i = 0 ; i<vertexNum ; i++)//初始化矩阵dist和path{for(j = 0 ; j<vertexNum ; j++){dist[i][j] = edge[i][j];if(dist[i][j]!=100)//假设权值最大为100path[i][j] = vertex[i]+vertex[j];elsepath[i][j] = "";}}for(k = 0 ; k<vertexNum ; k++)//n个顶点进行迭代,n个顶点分别插入到二维矩阵(path)的路径中看是否更新路径{for(i = 0 ; i<vertexNum ; i++)//二维矩阵的两层循环{for(j = 0 ; j<vertexNum ; j++){if(dist[i][k]+dist[k][j]<dist[i][j]){dist[i][j] = dist[i][k]+dist[k][j];path[i][j] = path[i][k]+paht[k][j];}}}}
}

n个顶点更新迭代n次，插入顶点k时，插入到除k行k列外的其他路径中才有意义。
实例：医院选址问题（《数据结构》课本P211）

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！