Now-2019.8.10
Dijkstra可以解決從起始點(diǎn)到終點(diǎn)的最短路徑問題匾浪；
常用的算法有 Dijkstra 跺涤， Floyd 匈睁， SPFA ;
該文章主要講的是 Dijkstra 算法；
Dijkstra算法是貪心思想的體現(xiàn)桶错，即不斷尋找最短的路徑航唆，并不斷更新（也稱 松弛）最終找到要找的出口。
所謂的松弛操作即是將已知到達(dá)的路徑 與 走過之后更新的路徑 相比院刁，如果有縮短糯钙，即可將新的路徑存儲到表中；
其中較為重要的 ：dis[maxn];//記錄目前的路徑長短
? ? ? ? ? ? ? ? ? bool? ? ?vis[maxn];//visit退腥？
有兩個數(shù)組任岸，dis和vis含義參見上面，初始時vis中只有起點(diǎn)狡刘，更新dis中的起點(diǎn)到所有點(diǎn)的距離.
遍歷所有節(jié)點(diǎn)享潜，找到距離起點(diǎn)最近的一個點(diǎn)K，將這個點(diǎn)加入vis中標(biāo)記
進(jìn)行松弛操作嗅蔬，遍歷沒有在vis數(shù)組中的其他所有點(diǎn)剑按，比較起點(diǎn)——>該點(diǎn)和起點(diǎn)——>K點(diǎn)——>該點(diǎn)的距離，
重復(fù)2-3操作澜术，直到所有的點(diǎn)遍歷完
#define INF 65535
int n,m,s,t;
int Chara[N][N],dis[N],vis[N],p[i];//chara為鄰接矩陣艺蝴；
void Dijkstra(int src)? //src傳入的起點(diǎn)
{
? ? for(int i=0; i<m; i++) //初始化起點(diǎn)到所有點(diǎn)的距離
? ? {
? ? ? ? dis[i] = Chara[src][i];
? ? ? ? vis[i] = 0;//設(shè)為false
? ? ? ? p[i]=0;
? ? }
? ? dis[src] = 0; //到自身距離為0
? ? vis[src] = 1; //標(biāo)記 注src=0
? ? for(int i=0; i<m; i++)
? ? {
? ? ? ? int ans = INF,k;
? ? ? ? for(int j=0; j<m; j++) // 尋找未被訪問過距離起點(diǎn)v0最近的
? ? ? ? {
? ? ? ? ? ? if(!vis[j] && dis[j] < ans)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? k = j;
? ? ? ? ? ? ? ? ans = dis[j];
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? vis[k] = 1;? //標(biāo)記已訪問
? ? ? ? if(ans == INF) break; //表示剩下所有點(diǎn)都不通
? ? ? ? for(int j =0; j<m; j++)? //松弛操作，更新起點(diǎn)到所有未訪問點(diǎn)的距離
? ? ? ? {
? ? ? ? ? ? if(!vis[j] &&? dis[k] + Chara[k][j]<dis[j] )
? ? ? ? ? ? {
? ? ? ? ? ? ? ? dis[j] = dis[k] + Chara[k][j];
? ? ? ? ? ? ? ? p[j]=k;//存放前驅(qū)節(jié)點(diǎn)
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
這是網(wǎng)上較為基礎(chǔ)的原始代碼鸟废，轉(zhuǎn)載：https://blog.csdn.net/qq_36932169/article/details/78806863
但是在真正寫題的時候猜敢，題目并不會讓寧把模板套上去就能用：例如 如果上面代碼中的N很大，毫無疑問將會失敽醒印缩擂；
這就需要將Dijkstra代碼進(jìn)行優(yōu)化。下面是 用優(yōu)先隊列 和 鄰接表 進(jìn)行? 的優(yōu)化兰英；
struct edge {
int from , to , w;//w is the cost;
edge(int a,int b,int c)from(a)...;
}撇叁；
vector<edge> e[NUM];
struct s_node{
? ? ? ? int id, n_dis;
? ? ? ? s_node(int a, int b) ...;
? ? ? ? bool operator < (const s_node &a) const{
? ? ? ? return n_dis>a.n_dis;
}
}
int pre[NUM];//
void Dijkstra()
{
?int s,dis[NUM];
bool visit[NUM];
for(1 to n)? dis[i]=inf;visit[i]=false;//? ? 初始化
dis[s]=0;//初始點(diǎn)到自身距離為0；
priority_queue<s_node>? Q;//優(yōu)先隊列
Q.push(s_node(s,dis[s]));//加入初始node? ?id= s畦贸，n_dis=0;
while(!Q.empty())
{
? ? ? ? ? ? s_node u= Q.top();
? ? ? ? ? ? Q.POP();
? ? ? ? ? ? if(!visit[u.id])//訪問過陨闹？
? ? ? ? ? ? ? ? ? ? continue;
? ? ? ? ? ? visit[u.id]=true;
? ? ? ? ? ? for(i=0;i<e[u.id].size();i++)
???????????{
? ? ? ? ? ? ? ? edge y = e[u.id][i];//查找與該點(diǎn)相鄰的點(diǎn)
? ? ? ? ? ? ? ? if(!visit[y.to])
? ? ? ? ? ? ? ? ? ? ? ? continue;
? ? ? ? ? ? ? ? if(dis[y.to]>y.w+ u.n_dis) // 松弛
? ? ? ? ? ? ? ? ? ? ? ? dis[y.to]=y.w+ u.n_dis ;
? ? ? ? ? ? ? ? ? ? ? ? Q.push(s_node(y.to,dis[y.to]));
? ? ? ? ? ? ? ? ? ? ? ? pre[y.to]=u.id;
????????????}
}
}
該代碼出自《算法競賽 入門到進(jìn)階》一書 P252 ；
