//============================================================================
// Name : Dijkstra.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include <stdio.h>
using namespace std;
#define MAXN 6
#define INF 100000
int n;
int map[MAXN][MAXN]; //定义一个 6*6 的图
int dist[MAXN]; //存储最短路径的 长度
int visit[MAXN]; //是否已求得最短路径
int path[MAXN]; //存储路径
//求start 到其他各点j的最短距离(存储在dist[j])
void dijkstra(int start)
{
for (int i = 0; i < MAXN; i++)
{
dist[i] = map[start][i];
visit[i] = 0; //初始化
if (i != start && dist[i] < INF)
path[i] = start; //用path记录路径
else
path[i] = -1;
}
visit[start] = 1;
dist[start] = 0; //存储从开始位置到其他位置的距离
for (int i = 0; i < MAXN - 1; i++)
{
int min = INF;
int u = start;
//选择当前集合T中具有最短路径的顶点u
for (int j = 0; j < MAXN; j++)
{
if (!visit[j] && dist[j] < min)
{
u = j;
min = dist[j];
}
}
visit[u] = 1; //当顶点u加入到集合S, 表示它的最短路径已经求得
/* 更新dist[] 和 path */
for (int k = 0; k < MAXN; k++)
{
//如果位置k 还为求得 && u可达k
if (!visit[k] && map[u][k] < INF)
{
int temp = dist[u] + map[u][k];
// 如果通过u到达k比原来的距离要短,就更新。
if (temp < dist[k])
{
dist[k] = temp;
path[k] = u;
}
}
}
}
}
int main()
{
// scanf("%d", &n);
int a, b, c;
for (int i = 0; i < 6; i++)
for (int j = 0; j < 6; j++)
map[i][j] = 100000;
//读入数据 a==-1 时结束
while (1)
{
scanf("%d %d %d", &a, &b, &c);
if (a == -1)
break;
map[a][b] = c;
}
int start = 0;
dijkstra(start); //求start 到其他各点j的最短距离(存储在dist[j])
//输出最短距离
for (int i = 0; i < MAXN; i++)
{
if (i != start)
{
printf("%d 到 %d 最短路径:", start, i);
int temp = i;
printf("%d", temp);
while (path[temp] != start)
{
temp = path[temp];
printf(" <- %d", temp);
}
printf(" <- %d ,长度: %d \n", start, dist[i]);
}
}
return 0;
}
/*
0 2 5
0 3 20
1 0 2
1 4 8
2 5 7
2 1 15
4 3 4
5 3 10
5 4 18
-1 -1 -1
*/
测试;
0 2 5
0 3 20
1 0 2
1 4 8
2 5 7
2 1 15
4 3 4
5 3 10
5 4 18
-1 -1 -1
0 到 1 最短路径:1 <- 2 <- 0 ,长度: 20
0 到 2 最短路径:2 <- 0 ,长度: 5
0 到 3 最短路径:3 <- 0 ,长度: 20
0 到 4 最短路径:4 <- 1 <- 2 <- 0 ,长度: 28
0 到 5 最短路径:5 <- 2 <- 0 ,长度: 12
分享到:
相关推荐
Dijkstra算法算是贪⼼思想实现的,⾸先把起点到所有点的距离存下来找个最短的,然后松弛⼀次再找出最短的,所谓的松弛操作就是,遍历⼀遍看通过刚刚找到的距离最短的点作为中转站会不会更近,如果更近了就更新距离,...
代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法...
dijkstra算法C++实现的程序代码
毕业设计:最短路径算法实现,Dijkstra算法,双向Dijkstra算法,CH算法,SILC算法 毕业设计:最短路径算法实现,Dijkstra算法,双向Dijkstra算法,CH算法,SILC算法 毕业设计:最短路径算法实现,Dijkstra算法,双向...
能够实现 Dijkstra算法,内涵代码,运行即可实现
Dijkstra算法应用举例 Dijkstra算法应用举例Dijkstra算法应用举例 Dijkstra算法应用举例
本程序使用C语言实现了Dijkstra算法。程序中,定义好邻接矩阵,可以计算出任一节点到其他所有节点的最短路径,并打印路径与长度。其中对最短路径的存储是依据所得到的生成树,可以减少内存空间占用。
Dijkstra算法的Matlab程序,用于求各点之间的最短路距离。该程序解决了一个有九个点的无向图中求任意两点之间最短路距离的例子。程序中的每一步都有详细说明。
文章研究了一种多核架构下基于OpenMP的Dijkstra并行算法,以Dijkstra算法为基础设计并行程序。对传统Dijkstra算法进行分析,明确优化方向,再利用OpenMP开发工具对并行程序进行优化调试。结果表明,文中算法易于操作...
Dijkstra算法求解格栅地图路径matlab代码
Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q,所以搜索Q中最小元素的运算(Extract-Min(Q))只需要线性搜索Q中的所有元素。这样的话算法的运行时间是O(n2)。
Dijkstra算法的应用, Dijkstra算法的应用 Dijkstra算法的应用 Dijkstra算法的应用 Dijkstra算法的应用 Dijkstra算法的应用 Dijkstra算法的应用
戴克斯特拉算法(Dijkstra’s algorithm)是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向...对于不含负权的有向图,Dijkstra算法是目前已知的最快的单源最短路径算法。
C语言版Dijkstra算法,有注释。 只是简单的Dijkstra算法的实现。
Dijkstra算法,Dijkstra算法详细讲解,Dijkstra算法详细讲解
Dijkstra算法是用于计算一个节点到其余所有节点最短路径的单源路径算法。我们先阐述Dijkstra算法的原理,在算法设计中,分别用邻接矩阵和邻接表存储带权有向图,并编写C++语言实现Dijkstra算法最短路径,用户只需...
最短路径Dijkstra算法-最短路Dijkstra算法.rar 最短路径Dijkstra算法
主要使用了Dijkstra算法,Floyd算法。 主要功能有六项:1、烟台大学的平面图。2、景点的介绍。3、从一个景点到其他地方的所有最短路径。4、两景点间的最短路径。5、计算从一个地方到另一个地方所要花费的时间。6、...
Dijkstra算法求最短路径的C/C++程序