Dijkstra最短路径
思路
首先选择一条最短路径前进
到达下一站后，判断出"走过的路程+当前位置到未曾到达过的多个邻居距离和"中选取最短路径前进，并更新出发点和当前位置邻居的距离
例如一个从0出发
-
首先在0判断去往哪个邻居路程最短 ，得知是<0,1>，路程为1，前进
-
前进到1后，走过的路程+去往未访问过的邻居(2、3)所需要的路程中
<0,3>距离:1+3=4
<0,2>距离:1+9=10
选择最短路径前进到3
-
前进到3后，走过的路程+去往未访问过的邻居(2、4、5)所需要的路程中
<0,2>距离:1+3+4=8<10，则更新<0,3>最短距离为8
<0,4>距离:1+3+13=17
<0,5>距离:1+3+15=19
选择最短路径前进到3
-
前进到2后，走过的路程+去往未访问过的邻居(只有4)所需要的路程中
<0,4>距离:1+3+4+5=13<17，则更新<0,4>最短距离为13
选择最短路径前进到4
-
前进到4后，走过的路程+去往未访问过的邻居(只有5)所需要的路程中
<0,5>距离:1+3+4+5+4=17<19，则更新<0,5>最短距离为17
选择最短路径前进到5
最短路径为：0 -> 1 -> 3 -> 2 -> 4 -> 5
最短距离为: 17
邻接矩阵存储结构
typedef struct Adjacenc_Matrix
{
int vex[MaxSize]; // 顶点数据数组
int T[MaxSize][MaxSize]; //邻接表
} Adjacenc_Matrix;
typedef struct data
{
bool visited[MaxSize]; //是否访问过的标志
int distance[MaxSize]; //存储到各个顶点的距离
int pre[MaxSize]; //当前节点的前驱节点
Adjacenc_Matrix Adj;
} data;
创建邻接表
bool CreateTable(data &d)
{
for (int i = 0; i < MaxSize; i++)
{
cin >> d.Adj.vex[i];
int j, weight;
while (true)
{
if (cin.get() == '\n')
{
break;
}
cin >> j >> weight;
d.Adj.T[i][j] = weight;
}
}
return true;
}
全部代码
#include <iostream>
#include <string>
using namespace std;
#define MaxSize 6
#define InitWeight 65535
typedef struct Adjacenc_Matrix
{
int vex[MaxSize];
int T[MaxSize][MaxSize];
} Adjacenc_Matrix;
typedef struct data
{
bool visited[MaxSize];
int distance[MaxSize];
int pre[MaxSize];
Adjacenc_Matrix Adj;
} data;
bool Init(data &d)
{
for (int i = 0; i < MaxSize; i++)
{
cin >> d.Adj.vex[i];
d.visited[i] = false;
d.pre[i] = -1;
d.distance[i] = InitWeight;
for (int j = 0; j < MaxSize; j++)
{
if (i == j)
{
d.Adj.T[i][j] = 0;
continue;
}
d.Adj.T[i][j] = InitWeight;
}
}
return true;
}
bool CreateTable(data &d)
{
for (int i = 0; i < MaxSize; i++)
{
cin >> d.Adj.vex[i];
int j, weight;
while (true)
{
if (cin.get() == '\n')
{
break;
}
cin >> j >> weight;
d.Adj.T[i][j] = weight;
}
}
return true;
}
void VisitAdj(data d)
{
printf("------------------邻接矩阵------------------\n");
for (int i = 0; i < MaxSize; i++)
{
for (int j = 0; j < MaxSize; j++)
{
printf("%d\t", d.Adj.T[i][j]);
}
printf("\n");
}
printf("------------------------------------------\n");
}
void Visit(data d)
{
for (int i = 0; i < MaxSize; i++)
{
printf("%d \t", d.visited[i]);
}
cout << endl;
for (int i = 0; i < MaxSize; i++)
{
printf("%d \t", d.distance[i]);
}
cout << endl;
for (int i = 0; i < MaxSize; i++)
{
printf("%d \t", d.pre[i]);
}
cout << endl;
}
//获取最短路径
bool GetShortestPath(data d, int start, int end)
{
printf("%d -> ", start);
int temp = start;
for (int i = 0; i < MaxSize; i++)
{
for (int j = 0; j < MaxSize; j++)
{
if (d.pre[j] == temp)
{
printf("%d", d.Adj.vex[j]);
temp = j;
if (d.Adj.vex[j] != end)
{
printf(" -> ");
}
else
{
printf("\n");
}
break;
}
}
}
printf("最短路径为:%d\n", d.distance[end]);
return true;
}
bool ShortestPath(data &d, int start, int end)
{
//初始化出发点到其他顶点的距离
d.visited[start] = true;
for (int j = 0; j < MaxSize; j++)
{
if (start != j && d.Adj.T[start][j] != InitWeight)
{
//标记出发点的邻居的前继为出发节点
d.pre[j] = start;
}
//存储出发点到邻居的距离
d.distance[j] = d.Adj.T[start][j];
}
for (int i = 0; i < MaxSize; i++)
{
printf("%d \t", d.visited[i]);
}
cout << endl;
for (int i = 0; i < MaxSize; i++)
{
printf("%d \t", d.distance[i]);
}
cout << endl;
for (int i = 0; i < MaxSize; i++)
{
printf("%d \t", d.pre[i]);
}
cout << endl;
//开始循环遍历
for (int b = 1; b < MaxSize; b++)
{
//获取最短路径和当前所在顶点的下标
int min = InitWeight;
int index;
for (int j = 0; j < MaxSize; j++)
{
//选取一条顶点没有遍历过的最短路径
if (d.distance[j] < min && !d.visited[j])
{
min = d.distance[j];
index = j;
}
}
printf("min:%d index:%d\n", min, index);
//更新当前顶点到邻居的距离
d.visited[index] = true;
for (int k = 0; k < MaxSize; k++)
{
//如果邻居顶点没有遍历过，并且前面走过的路径加上将要走的路径 小于 其他到达邻居的路径，则更新最短距离
if (!d.visited[k] && d.distance[index] + d.Adj.T[index][k] <= d.distance[k])
{
d.distance[k] = d.distance[index] + d.Adj.T[index][k];
d.pre[k] = index;
}
}
//自己的写法
// for (int k = 0; k < MaxSize; k++)
// {
// //如果下一步是要去邻居
// if (d.Adj.T[index][k] != InitWeight)
// {
// //则更新到达邻居的距离
// d.distance[k] = min + d.Adj.T[index][k];
// //并且更改下一步去往的邻居前继顶点下标为当前顶点的下标
// if (k != index && d.visited[k] != true)
// {
// d.pre[k] = index;
// }
// }
// }
printf("----------------------------------------------\n");
Visit(d);
}
GetShortestPath(d, start, end);
return true;
}
int main()
{
/*
0 1 2 3 4 5
0 1 1 2 12
1 2 9 3 3
2 4 5
3 2 4 4 13 5 15
4 5 4
5
*/
data d;
Init(d);
CreateTable(d);
VisitAdj(d);
ShortestPath(d, 0, 5);
}
转载：https://blog.csdn.net/weixin_46079657/article/details/115983026
查看评论