Dijkstra演算法
定義：迪克斯特拉演算法，是從一個頂點到其余各頂點的最短路徑演算法，解決的是有權圖中最短路徑問題，迪杰斯特拉演算法主要特點是從起始點開始，采用貪心演算法的策略，每次遍歷到始點距離最近且未訪問過的頂點的鄰接節點，直到擴展到終點為止，
Dijkstra(迪杰斯特拉)演算法是典型的單源最短路徑演算法
同時這個有權圖中不能出現負邊，
這里解決單源最短路徑問題需要先了解Dijkstra演算法，所以這里先把個人對于這個演算法的理解附上，再解決最短路問題，
以這個圖為例，從1號走到7號的最短路徑明顯是從1到4再到7，這條路徑的權值最小，從代碼角度就要利用Dijkstra演算法來解釋，
因為是從1號開始走，所以把所有與1號直接相連點，都記錄下來，從1無法直接走到的點，其權值都暫時標記為無窮大，這時發現能走的點當中，權值最小的路徑是走到2號，這個時候就走到2號，并把2號標記為走過，
這個時候，再檢索，與1號和2號直接相連的所有點，不是直接相連的的權值暫時都記為無窮，這是5號、3號、4號都是直接相連的，走到這些點的對應權值總和是4、2、3，這里說一下5這個點，到5號權值之所以是4，是因為把2號當成中轉站了，也就是1->2->5這么走的， 這里又開始選權值最小的路徑，那當然是選1->3這條路，走到3號并把3號標記為走過，
把2號和3號當成中轉站，開始檢索與1、2、3號直接相連的點，并選出權值最小的路徑、并重繪到每個點的權值，（無法直接到點，到那個點的路徑權值暫時標記為無窮，意味著暫時走不到） 到5、6、3號的路徑權值分別為4、8、3，所以到4號，
來到4號，再重復上述操作，到5、6、7的路徑權值分別為4、8、7，所以選7號，走過去，
此時，已經到了目標點7號，但是，所有的點還沒走完，所以接著走，
到了這里相信大家都知道該怎么做了，就是照著葫蘆畫瓢，把走過的路徑當成中轉站，檢索所有可以直接走過去的點、計算出到那個點的權值、選出路徑權值最小的一條，去走，最后又開始，調整到每個點的路徑權值（因為走了一個點，就又多了一個中轉站）
最后，圖會呈現這樣的狀態，而到每個點的路徑權值都計算出來了，也記錄了到每個點的路徑最小權值，
總結一下就是，先檢索每個能直接相連的點 （與中轉站相連也算直接相連） ,并選出路徑權值最小的那個點，走過去，標記那個點走過了，接著把那個點當成中轉站，調整一下到每個點的路徑權值，無法直接走到的點的路徑權值就記為無窮大（意思就是暫時還走不到那個點），如此反復，直到所有點都走過了為止，
因為每次選的都是路徑權值最小的，所以到目標點的路徑權值一定是最小的，
這里把走過的點當成中轉站，是一種理解，也可以把走過的點看成一個整體，當成一個大的點，也可以當成把那個點吞了之類的，怎么好想怎么來吧，
圖結構練習——最短路徑
Description
給定一個帶權無向圖，求節點1到節點n的最短路徑，
Input
輸入包含多組資料，格式如下，
第一行包括兩個整數n m，代表節點個數和邊的個數，(n<=100)
剩下m行每行3個正整數a b c，代表節點a和節點b之間有一條邊，權值為c，
Output
每組輸出占一行，僅輸出從1到n的最短路徑權值，（保證最短路徑存在）
Sample
Input
3 2
1 2 1
1 3 1
1 0
Output
1
0
#include<bits/stdc++.h>
#include<string.h>
using namespace std;
#define inf 0x3f3f3f3f
int mp[111][111]; //圖
bool vis[111]; //標記是否走過
int point[111]; //用來到某個點需要的權值
void dijkstra(int n)
{
int i,j,k,min,u;
for(i=1;i<=n;i++) //因為是從1開始
{
point[i]=mp[1][i];//先把與1相連的所有的點的權值，都記錄下來
} //不相連的那些點記錄進去的是無窮，但不影響后面的判斷，因為是找最小的，所以無窮不影響判斷
vis[1]=1; //1點標記為走過了
for(i=1;i<n;i++)//進行n-1次查詢
{
min=inf;
for(j=1;j<=n;j++)
{
if(min>point[j]&&!vis[j]) //那個點沒被走過的情況下，開始找最小的權值，并把那個點記錄下來
{
min=point[j];
u=j;
}
}
vis[u]=1;//找到的那個點，標記走過了
for(k=1;k<=n;k++) //開始調整到n個點的權值
{
if(!vis[k]&&mp[u][k]<inf&&point[k]>mp[u][k]+point[u]) //在那個點沒被走的情況下，從當前點能走到那個點的情況（廢話，能走才會走過去）
{ //把當前記錄的權值，與加入新點后走到那個點所需要的權值進行比較，記錄小的那個
point[k]=mp[u][k]+point[u];
}
}
}
printf("%d\n",point[n]); //最后輸出走到n點需要的總權值
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
memset(vis,0,sizeof(vis));//初始化
memset(mp,inf,sizeof(mp)); //先把圖中到所有點的步數都記為無窮
memset(point,inf,sizeof(point));
for(int i=1;i<=n;i++) //當前點到當前點的步數記為0
{
mp[i][i]=0;
}
while(m--)//開始讀入圖
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(mp[x][y]>z)//這里是為了防止路徑覆寫
{ //比如說同一條路重復了2次但是路徑數不一樣，那肯定是記錄小的那個
mp[x][y]=mp[y][x]=z;
}
}
dijkstra(n); //把終點傳過去
}
return 0;
}
這里的代碼也是參考了學校里的學長和csdn的大佬，
如果你有任何建議或者批評和補充，請留言指出，不勝感激，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/261879.html
標籤：其他