请给出C++代码:设计实现有向网结构,针对随机有向网实例和随机源点,用Dijkstra算法求解出单源点到其他各顶点的最短路径,给出求解过程的动态演示。
时间: 2023-03-15 21:01:13 浏览: 123
matlib.zip_dijkstra_图的最短路径_有向图_有向图 最短路径
5星 · 资源好评率100%
#include<stdio.h>
#define MAX 100 int G[MAX][MAX]; //定义有向网结构存储矩阵
int dis[MAX]; //存放源点到其他各顶点的最短距离
int visited[MAX]; //标记顶点是否已被访问
int n; //有向网结构中顶点的个数//从有向网结构G中,找到源点到其他各顶点的最短路径
void Dijkstra(int v0)
{
int i;
for (i = 0; i < n; i++)
{
dis[i] = G[v0][i]; //记录源点到其他各顶点的距离
visited[i] = 0; //初始化每个顶点都未被访问
}
visited[v0] = 1; //源点被访问过
int min;
int u;
int count = 1;
while (count < n)
{
min = INF;
for (i = 0; i < n; i++)
{
if (visited[i] == 0 && dis[i] < min)
{
min = dis[i];
u = i;
}
}
visited[u] = 1;
count++;
for (i = 0; i < n; i++)
{
if (visited[i] == 0 && dis[i] > dis[u] + G[u][i])
{
dis[i] = dis[u] + G[u][i];
}
}
}
}
阅读全文