参考：Dijkstra算法
数据结构来到了图论这一章节，网络中的路由算法基本都和图论相关。于是在拿到DS的实验题的时候，决定看下久负盛名的Dijkstra算法。
Dijkstra的经典应用是开放最短路径优先路由算法(OSPF)。
题目：
第一种实现的算法(错误)：
在看过相关的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