最短路径
问题抽象：在有向网中A点到达B点的多条路径中，寻找一条各边权值之和最小的路径。
- 第一类问题：两点间的最短路径（单源最短路径）——Dijkstra算法。
- 第二类问题：某源点到其他各点最短路径（所有顶点间的最短路径）——Floyd算法。
Dijkstra算法
算法流程
- 首先找到与源点
到所有顶点的路径w(
)，无法直达的顶点路径设为∞。
- 在这些路径中找出一条长度最短的路径(
)
- 更新各个路径：若图中存在弧(
)，且w(
)，则以路径(
)代替(
- 在更新后的各条路径中，寻找长度最短的路径，以此类推直至所有顶点均被访问。
时间复杂度：O()
C语言实现
void Dijkstra(Graph G, int v){
//Visited数组用于表示节点是否被访问
int* Visited = (int*)malloc(sizeof(int)*G->vexnum);
//Distance数组用于表示起始点到各个节点的最短距离
int* Distance = (int*)malloc(sizeof(int)*G->vexnum);
//Parent数组用于表示当前节点的前驱
int* Parent = (int*)malloc(sizeof(int)*G->vexnum);
for(int i = 0; i < G->vexnum; i++){//初始化三个数组
Visited[i] = 0;
Distance[i] = MAXINT;
Parent[i] = -1;
}
Visited[v] = 1;
Distance[v] = 0;
Parent[v] = -2; //起始点的父节点设置为-2
int visitednum = 1, cur = v; //设置当前节点为v
while(visitednum < G->vexnum){
//Update
for(int i = 0; i < G->vexnum; i++){//若从起始点到当前节点的距离与边的权值之和小于此节点的距离则更新
if(Visited[i] == 0 && (G->arcs[cur][i] + Distance[cur] < Distance[i])){
Distance[i] = G->arcs[cur][i] + Distance[cur];
Parent[i] = cur;
}
}
//Scan
int Min = MAXINT, add = -1;
for(int i = 0; i < G->vexnum; i++){//找出未访问的节点中距离最小的节点
if(Visited[i] == 0 && Distance[i] < Min){
Min = Distance[i];
add = i;
}
}
//Add
Visited[add] = 1;//将未访问的节点中距离最小的设置为已访问
visitednum++;//更新已访问的节点数
cur = add;
}
for(int i = 0; i < G->vexnum; i++){//打印最短距离
printf("%d ", Distance[i]);
}
printf("\n");
for(int i = 0; i < G->vexnum; i++){//打印父节点信息
printf("%d ", Parent[i]);
}
}
Floyd算法
算法思想
- 逐个顶点试探
- 从
到
的所有可能存在的路径中
- 选出一条长度最短的路径
算法流程
- 初始时设置一个n阶距离方阵，令其对角线元素为0，若存在弧<
>，则对应元素为权值，否则为∞。
- 逐步试着在原直接路径中增加中间顶点，若加入中间顶点后路径变短，则修改之，否则维持原值，所有顶点试探完毕，算法结束。即对图中的每一个顶点
，查看w(
)+w(
)的长度是否小于w(
时间复杂度：O()
C语言实现
void Floyd(Graph G){
//分配空间
int** Distance = (int**)malloc(sizeof(int*)*G->vexnum);
for(int i = 0; i < G->vexnum; i++)Distance[i] = (int*)malloc(sizeof(int)*G->vexnum);
int** Source = (int**)malloc(sizeof(int*)*G->vexnum);
for(int i = 0; i < G->vexnum; i++)Source[i] = (int*)malloc(sizeof(int)*G->vexnum);
for(int i = 0; i < G->vexnum; i++){
for(int j = 0; j < G->vexnum; j++){
Distance[i][j] = G->arcs[i][j];
if(i != j)Source[i][j] = j;
else Source[i][j] = -1;
}
}
//算法主体
for(int k = 0; k < G->vexnum; k++){
for(int i = 0; i < G->vexnum; i++){
for(int j = 0; j < G->vexnum; j++){
if(Distance[i][k] + Distance[k][j] < Distance[i][j]){
Distance[i][j] = Distance[i][k] + Distance[k][j];
Source[i][j] = Source[i][k];
}
}
}
}
//打印距离矩阵
printf("Distance Matrix:\n");
for(int i = 0; i < G->vexnum; i++){
for(int j = 0; j < G->vexnum; j++){
printf("%5d", Distance[i][j]);
}
printf("\n");
}
//打印路径矩阵
printf("Source Matrix:\n");
for(int i = 0; i < G->vexnum; i++){
for(int j = 0; j < G->vexnum; j++){
printf("%5d", Source[i][j]);
}
printf("\n");
}
//释放空间
for(int i = 0; i < G->vexnum; i++){
free(Distance[i]);
free(Source[i]);
}
free(Distance);
free(Source);
}
