- 適合不含負(fù)權(quán)邊的單源最短路
- S：已找到的到源點(diǎn)的集合
- dis[i]：頂點(diǎn)i到源點(diǎn)的最短路徑距離
- 每次取不在S中dis最小的點(diǎn)v候醒，將v加入S， 并更新各點(diǎn)dis值
偽代碼
1.初始化S谷扣，將源點(diǎn)加入S
2.初始化dis吮龄，與源點(diǎn)有連接的為那條邊的值丽旅，否則為無窮大
while（S不包含所有頂點(diǎn)）
{
u=min{dis[u]|u不在S中}
u加入S
for（每個(gè)不在S中的點(diǎn)v&&dis[v]>dis[u]+w（uv））
dis[v]=dis[u]+w（uv）;
}
時(shí)間復(fù)雜度為O（n^2）染服，因?yàn)檎襍外的dis最小點(diǎn)要耗費(fèi)O（n）
此處用堆來優(yōu)化可降到O（nlgn）
HDU 2544
Problem Description
在每年的校賽里，所有進(jìn)入決賽的同學(xué)都會獲得一件很漂亮的t-shirt奔坟。但是每當(dāng)我們的工作人員把上百件的衣服從商店運(yùn)回到賽場的時(shí)候携栋，卻是非常累的！所以現(xiàn)在他們想要尋找最短的從商店到賽場的路線咳秉，你可以幫助他們嗎婉支？
Input
輸入包括多組數(shù)據(jù)。每組數(shù)據(jù)第一行是兩個(gè)整數(shù)N滴某、M（N<=100磅摹，M<=10000），N表示成都的大街上有幾個(gè)路口霎奢，標(biāo)號為1的路口是商店所在地户誓，標(biāo)號為N的路口是賽場所在地，M則表示在成都有幾條路幕侠。N=M=0表示輸入結(jié)束帝美。接下來M行，每行包括3個(gè)整數(shù)A晤硕，B悼潭，C（1<=A,B<=N,1<=C<=1000）,表示在路口A與路口B之間有一條路庇忌，我們的工作人員需要C分鐘的時(shí)間走過這條路。
輸入保證至少存在1條商店到賽場的路線舰褪。
Output
對于每組輸入皆疹，輸出一行，表示工作人員從商店走到賽場的最短時(shí)間
Sample Input
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
Sample Output
3
2
思路：
用優(yōu)先隊(duì)列來優(yōu)化最小距離的查找
優(yōu)先隊(duì)列中的每一項(xiàng)是表示該店的下標(biāo)和dis的結(jié)構(gòu)體
用二維數(shù)組來存圖
定義一維數(shù)組visited存點(diǎn)是否被訪問過占拍，dis存距離源點(diǎn)的距離
首先每次執(zhí)行時(shí)都要初始化這幾個(gè)數(shù)組略就，visited全是0，dis全是一個(gè)超大的值晃酒，二維數(shù)組對角線0其他-1
dijkstra算法表牢，將源點(diǎn)入隊(duì)，并且源點(diǎn)的dis要設(shè)為0（這步容易漏）贝次，while循環(huán)崔兴，隊(duì)列非空，并且終點(diǎn)還未被訪問過
找出隊(duì)列中優(yōu)先級最高（即dis最谢壮帷）且未被訪問過點(diǎn)
訪問設(shè)為是
對每個(gè)結(jié)點(diǎn)判斷是否未被訪問過與剛才找到的點(diǎn)是否有連接是否能使dis變小
如果可以更新dis敲茄，并入隊(duì)
pop剛才訪問的那個(gè)點(diǎn)
#include <iostream>
#include <queue>
#include <cstring>
#define N 110
#define INF 999999
using namespace std;
struct node {
//優(yōu)先隊(duì)列中的結(jié)點(diǎn)
int num;//點(diǎn)的編號
int val;//到源點(diǎn)的距離
friend bool operator<(node a, node b) {
return a.val>b.val;
}
};
int dis[N];//存到源點(diǎn)的距離
int edge[N][N];//存邊的權(quán)值
int visited[N];//存是否被訪問過
int v, e;
priority_queue<node> que;
int Dijkstra(int s, int t)
{
//s源點(diǎn)，t終點(diǎn)
node n;
dis[s] = 0;//注意這部別漏了
n.num = s; n.val = 0;
que.push(n);
while (!que.empty() && (!visited[t])) {
while (visited[que.top().num]) que.pop();
visited[que.top().num] = 1;
for (int i = 1; i <= v; ++i) {
if ((!visited[i]) && edge[que.top().num][i] != -1)
if (dis[i]>dis[que.top().num] + edge[que.top().num][i]) {
dis[i] = dis[que.top().num] + edge[que.top().num][i];
n.num = i; n.val = dis[i];
que.push(n);
}
}
que.pop();
}
return dis[t];
}
int main()
{
cin >> v >> e;
while (v + e) {
memset(dis, INF, sizeof(dis));
memset(edge, -1, sizeof(edge));
memset(visited, 0, sizeof(visited));
while (!que.empty()) que.pop();
for (int i = 1; i <= v; ++i)
{
edge[i][i] = 0;
}
for (int i = 1; i <= e; ++i)
{
//讀圖而且重下標(biāo)1開始存
int beg, en, wgt;
cin >> beg >> en >> wgt;
edge[beg][en] = edge[en][beg] = wgt;
}
cout << Dijkstra(1, v) << endl;
cin >> v >> e;
}
return 0;
}
