DS实验题 Dijkstra算法

参考:Dijkstra算法

数据结构来到了图论这一章节,网络中的路由算法基本都和图论相关。于是在拿到DS的实验题的时候,决定看下久负盛名的Dijkstra算法。

Dijkstra的经典应用是开放最短路径优先路由算法(OSPF)。

题目:

DS实验题 Dijkstra算法

DS实验题 Dijkstra算法

第一种实现的算法(错误):

在看过相关的Dijkstra算法解析之后,决定自己尝试写个算法,不过很遗憾,考虑并不全面,理解也不是特别深刻。

最后决定还是贴出来。

算法思想:

1.建立邻接表(后面用二维数组实现,相对来说轻松很多)

2.维护三个数组:dist代表从源点到某个节点的最短路径长度;ins代表这个节点是否已经被查询过;pre记录最短路径。

3.算法主体:

-1.当前节点 = 源节点。

-2.从当前节点出发,遍历邻接节点,找到离它最近的节点,且这个节点尚未遍历过,同时更新dist。

-3.跳转到找到的最近节点,先前节点的ins置1,回到2。

-4.当当前节点附近没有未遍历的节点时,break。

算法代码如下:

//
// main.cpp
// Gank_Dijkstra
//
// Created by wasdns on 16/11/15.
// Copyright © 2016年 wasdns. All rights reserved.
// #include <cstdio>
#include <iostream>
#include <string.h>
#include <string>
#include <stack>
using namespace std;
#define maxn 100000000; struct edge {
edge *next;
int num;
int len;
} eg[100000]; struct head {
edge *next;
int num;
} h[100000]; void IniList(int n)
{
int i; for (i = 1; i <= n; i++)
{
h[i].next = NULL;
h[i].num = i;
}
} void CreatList(int n, int m)
{
int i;
int x, y, leng; for (i = 1; i <= n; i++)
{
h[i].next = NULL;
h[i].num = i;
} for (i = 0; i < m; i++)
{
cin >> x >> y >> leng; edge *p1, *p2; p1 = new edge;
p1 -> next = NULL;
p1 -> num = y;
p1 -> len = leng; p2 = new edge;
p2 -> next = NULL;
p2 -> num = x;
p2 -> len = leng; edge *p3, *p4; p3 = h[x].next; if (p3 == NULL) {
h[x].next = p1;
} else
{
while (p3 -> next != NULL) {
p3 = p3 -> next;
} p3 -> next = p1;
} p4 = h[y].next; if (p4 == NULL) {
h[y].next = p2;
} else
{
while (p4 -> next != NULL) {
p4 = p4 -> next;
} p4 -> next = p2;
}
}
} void PrintList(int n)
{
int i;
edge *p; for (i = 1; i <= n; i++)
{
p = h[i].next; cout << "Node:" << h[i].num << endl; while (p != NULL) {
cout << p -> num << " " << p -> len << " ";
p = p -> next;
} cout << endl;
}
} int pre[105]; int dist[105]; bool ins[105]; void Initial(int b, int n)
{
int i; memset(pre, -1, sizeof(pre)); for (i = 1; i <= n; i++)
{
dist[i] = 10000000; ins[i] = false;
} dist[b] = 0; pre[b] = b;
} int Dijkstra(int b, int n, int end)
{
Initial(b, n); int cnt = 0;
int turn = b; while (cnt < n)
{
edge *p;
p = h[turn].next; int minlen = maxn;
int tnext = turn; while (p != NULL)
{
if (ins[p -> num]) {
p = p -> next; continue;
} int t = dist[turn] + p -> len; if (t < dist[p -> num]) {
dist[p -> num] = t; pre[p -> num] = turn;
} if (t < minlen) {
minlen = t; tnext = p -> num;
} p = p -> next;
} ins[turn] = true; cnt++; if (turn == tnext) {
turn = b;
} turn = tnext;
} return dist[end];
} int main()
{
int n, m, s, e; cin >> n >> m >> s >> e; CreatList(n, m); PrintList(n); cout << Dijkstra(s, n, e) << endl; return 0;
} /* 5 6 1 5
1 2 5
2 5 5
1 3 3
3 5 7
1 4 1
4 5 9 6 9 1 6
1 3 3
1 2 6
2 3 2
2 4 5
3 4 3
3 5 4
4 5 2
4 6 3
5 6 5 5 6 1 5
1 2 7
1 3 1
1 4 3
2 5 1
3 5 10
4 5 9 */

算法缺陷:

测试一下下面这个样例,

 5 6 1 5
1 2 7
1 3 1
1 4 3
2 5 1
3 5 10
4 5 9

答案应该为8,但是结果为11。

原因在于,当以上算法经过:1 -> 3 -> 5 -> 2 最终来到节点2的时候,节点2附近没有未遍历的节点了(节点2),跳出循环。

第二种算法:

//
// main.cpp
// Dijkstra
//
// Created by wasdns on 16/11/16.
// Copyright © 2016年 wasdns. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <string.h>
using namespace std; int DijGraph[105][105]; //节点i和j之间的距离:DijGraph[i][j] int pre[105]; //最短路节点的前继节点(查询最短路) int dist[105]; //源点到每个节点的最短路距离 bool ins[105]; //节点i是否位于已查询节点集合S /*
初始化函数
*/ void Initial(int n)
{
for (int i = 1; i <= n; i++)
{
ins[i] = false; pre[i] = -1; for (int j = 1; j <= n; j++) { if (i == j) DijGraph[i][j] = 0; else DijGraph[i][j] = 1000000;
}
}
} int cnt = 1; //记录到目的节点的条数
int belen = 1000000; //到目的节点的最短路长度 void Dijkstra(int n, int b, int e)
{
int i, j; for (i = 1; i <= n; i++) { //根据图的信息初始化dist数组
dist[i] = DijGraph[b][i];
} dist[b] = 0;
ins[b] = true; //源节点加入集合S for (i = 2; i <= n; i++) //集合V一共有n-1个节点
{
int next = b; //记录此时V中最靠近源点的节点
int minlen = 1000000; //以及源点到该节点的长度 for (j = 1; j <= n; j++) //源点从V中挑一个最近节点
{
if (ins[j]) continue; //这个节点在S中,跳过 if (dist[j] < minlen) { //找到一个目前到源点距离最小的 next = j; minlen = dist[j]; //更新离源点最近节点的信息
}
} ins[next] = true; //最近节点离开V加入S for (j = 1; j <= n; j++) //新来的节点向外得到路径信息
{ //并维护dist
if (ins[j]) continue; /* 从源点到当前节点next的距离 + 当前节点next到某个相邻节点j的距离。*/
/* 如果小于目前源点到节点j的最短距离dist[j],更新dist[j]。*/ /* 另外,需要在这个时候记录到目的点的最短距离,以及路径条数。*/ int t = dist[next] + DijGraph[next][j]; if (t <= dist[j])
{
if (t < dist[j])
{
dist[j] = t; pre[j] = next; if (j == e) { cnt = 1; belen = dist[j];
}
} else
{
if (j == e) cnt++;
}
}
}
}
} int main()
{
int i, n, m, s, e; cin >> n >> m >> s >> e; int x, y, len; Initial(n); for (i = 1; i <= m; i++) { cin >> x >> y >> len; DijGraph[x][y] = len;
DijGraph[y][x] = len;
} Dijkstra(n, s, e); cout << belen << " " << cnt << endl; return 0;
}

2016/11/15

上一篇:dataGridViewX和数据库的链接之dataGridViewX1.DataSource = ds.Tables[0];


下一篇:DS Tree 已知后序、中序 => 建树 => 求先序