By yusijia

Updated:

Contents
  1. 1. 模板
  2. 2. hdu 2544题解

  • dijkstra算法解决的是单源点到其他顶点的最短路径问题，不能处理带有负权的图

  • 复杂度O(n^2)

  • prime算法是维护集合到点的最短距离

  • 迪杰斯特拉算法是维护点到点的最短距离

该算法要求图中不存在负权边
该算法还可以用堆优化来保存源点到Vb中所有点的距离并维护其最小值(源点s到u的最短路径已经确定，则点u属于集合Va，否则属于Vb)

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

//prime算法是维护集合到点的最短距离
//迪杰斯特拉算法是维护点到点的最短距离

/*
清除所有点的标号
设dis【start】 = 0， 其他dis【i】 = inf；
循环nodeNUm次{
    在所有未标号节点中，选出dis[]值最小的结点x
    给结点x标记
    对于从x除法的所有边(x, y)更新d[y] = min(d[y]， d[x] + w(x, y));
}
*/



//dijkstra算法求最短路，单源最短路，不能处理带有负权的图
//思想为单源点加入集合，更新dis[]数组，每次取dis[]最小的那个点，加入集合，再次更新dis[]数组，取点加入集合，直到所有的点都加入集合中

//可以在求出最短路径长的同时记录最短路径，这样只要倒着查回去就能确定整条最短路径


#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

const int maxNodeNum=110;//最多节点个数
const int maxEdgeNum=10010;//最多边条数

const int inf=0x3f3f3f3f;   //等于 十进制 1061109567,所以两倍不会超int
//inf一般设成这个而不是0x7f7f7f7f(其十进制为2139062143.),
//防止dis[MinNumber] + mp[MinNumber][j]溢出

//也可以这样
	      /*if(mp[MinNumber][j]<INF)//在这里加个判断来防止溢出
                {
                    if(dis[j]>dis[MinNumber]+mp[MinNumber][j])
                    {
                        dis[j]=dis[MinNumber]+mp[MinNumber][j];

                    }
                }*/

int nodeNum,edgeNum;//节点，有向边个数
int mp[maxNodeNum][maxNodeNum];//建立邻接矩阵
int dis[maxNodeNum];//dis[i]为源点到i的最短路径
int father[maxNodeNum];//存前驱
bool vis[maxNodeNum];//判断某个节点是否已加入集合

void dijkstra(int start)
{
  //**第一步：初始化，dis[]为最大，vis均为0（都未加入集合）,初始化father数组
  memset(dis,inf,sizeof(dis));
  memset(vis,0,sizeof(vis));
  for(int i = 0; i < nodeNum; i++){
    father[i] = i;
  }
  dis[start]=0;
  //**第二步：找dis[]值最小的点，加入集合，并更新与其相连的点的dis[]值

  //一开始集合里没有任何点，下面的循环中，第一个找到的点肯定是源点
  for(int i=1;i<=nodeNum;i++)
  {
    //寻找dis[]最小的点，加入集合中
    int MinNumber = -1,Min=inf;//MinNumber为dis[]值最小的点的编号
    for(int j=1;j<=nodeNum;j++) if(!vis[j] && dis[j]<Min){
        Min=dis[j];
        MinNumber=j;
    }
    if(MinNumber == -1)//如果没有点可以扩展，即剩余的点不可达，返回
	break;
    //找到dis[]最小的点，加入集合，更新与其相连的点的dis值
    vis[MinNumber]=1;
    for(int j=1;j<=nodeNum;j++)if(!vis[j] && mp[MinNumber][j] != inf){//没访问过j点且MinNumber到j有边
      dis[j] = min(dis[j], dis[MinNumber] + mp[MinNumber][j]);
      father[j] = MinNumber;
    }
  }
}

void printPath(int e)//参数是终点
{
    if(e != father[e]){
        printPath(father[e]);
        cout << "->" << e;
    }
    else{
        cout << e;
    }
}

int main()
{
  while(cin>>nodeNum>>edgeNum&&(nodeNum||edgeNum))
  {
    int from,to,w;
    memset(mp,inf,sizeof(mp));//初始化
    for(int i=1;i<=edgeNum;i++)//无向图，一条无向边看为两条有向边
    {
      cin>>from>>to>>w;
      if(w<mp[from][to])
        mp[from][to]=mp[to][from]=w;
    }
    dijkstra(1);
    cout<<dis[nodeNum]<<endl;
    printPath(nodeNum);
  }
  return 0;
}

输入：
5 5
1 2 1
2 3 2
3 5 1
1 4 1
4 5 1

输出：
1->4->5

hdu 2544题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

/*
清除所有点的标号
设dis【start】 = 0， 其他dis【i】 = inf；
循环nodeNUm次{
    在所有未标号节点中，选出dis[]值最小的结点x
    给结点x标记
    对于从x出发的所有边(x, y)更新d[y] = min(d[y]， d[x] + w(x, y));
}
*/


//思想为单源点加入集合，更新dis[]数组，每次取dis[]最小的那个点，加入集合，再次更新dis[]数组，取点加入集合，直到所有的点都加入集合中

//可以在求出最短路径长的同时记录最短路径，这样只要倒着查回去就能确定整条最短路径

#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
const int maxNodeNum = 110;//最多节点个数
const int maxEdgeNum = 10010;//最多边条数

const int inf = 0x3f3f3f3f;   //等于 十进制 1061109567,所以两倍不会超int
//inf一般设成这个而不是0x7f7f7f7f(其十进制为2139062143.),
//防止dis[MinNumber] + mp[MinNumber][j]溢出

//也可以这样
	      /*if(mp[MinNumber][j] < INF)//在这里加个判断来防止溢出
                {
                    if(dis[j] > dis[MinNumber] + mp[MinNumber][j])
                    {
                        dis[j] = dis[MinNumber] + mp[MinNumber][j];

                    }
                }*/

int nodeNum,edgeNum;//节点，有向边个数
int mp[maxNodeNum][maxNodeNum];//建立邻接矩阵
int dis[maxNodeNum];//dis[i]为源点到i的最短路径
bool vis[maxNodeNum];//判断某个节点是否已加入集合

void dijkstra(int start)
{
  //**第一步：初始化，dis[]为最大，vis均为0（都未加入集合）
  memset(dis, inf, sizeof(dis));
  memset(vis, 0, sizeof(vis));
  dis[start] = 0;
  //**第二步：找dis[]值最小的点，加入集合，并更新与其相连的点的dis[]值

  //一开始集合里没有任何点，下面的循环中，第一个找到的点肯定是源点
  for(int i = 1; i <= nodeNum; i++)
  {
    //寻找dis[]最小的点，加入集合中
    int MinNumber = -1,Min=inf;//MinNumber为dis[]值最小的点的编号
    for(int j = 1; j <= nodeNum; j++) if(!vis[j] && dis[j] < Min){
        Min = dis[j];
        MinNumber = j;
    }
    if(MinNumber == -1)//如果没有点可以扩展，即剩余的点不可达，返回
	     break;
    //找到dis[]最小的点，加入集合，更新与其相连的点的dis值
    vis[MinNumber] = 1;
    for(int j = 1; j <= nodeNum; j++) if(!vis[j] && mp[MinNumber][j] != inf)//没访问过j点且MinNumber到j有边
      dis[j] = min(dis[j], dis[MinNumber] + mp[MinNumber][j]);
  }
}


int main()
{
  while(cin >> nodeNum >> edgeNum && (nodeNum || edgeNum))
  {
    int from, to, w;
    memset(mp, inf, sizeof(mp));//初始化
    for(int i = 1; i <= edgeNum; i++)//无向图，一条无向边看为两条有向边
    {
      cin >> from >> to >> w;
      if(w < mp[from][to])
        mp[from][to] = mp[to][from] = w;
    }
    dijkstra(1);
    cout << dis[nodeNum] << endl;
  }
  return 0;
}
Contents
  1. 1. 模板
  2. 2. hdu 2544题解