#include <iostream>
#include <stdio.h>
using namespace std;
#define MAXVEX 100
#define INF 6000
//定義比較的數(shù)字 表示無(wú)窮大 只要比你圖中的權(quán)值運(yùn)算涉及的值要大就可以了
/************************************************************************/
/* Dijkstra 算法思想
/* 1: 基本思想就是貪心法（核心思想） --->在寫(xiě)代碼時(shí)候再說(shuō)
/* 2: 這里就是找出源點(diǎn)到各個(gè)點(diǎn)最短距離 然后用這個(gè)最短距離+源點(diǎn)到另外一個(gè)點(diǎn)距離 如果< 就修改值這樣不斷修改就得出了
/************************************************************************/
void Dijkstra(int graph[][MAXVEX],int startVex,int VexNum)
{
int path[MAXVEX] = {-1}; //保存最終點(diǎn)最短路徑的前一個(gè)點(diǎn)
int dist[MAXVEX] = {0};
int s[MAXVEX] = {0}; //標(biāo)志是否在s的集合中--> 這里要涉及到Dijkstra 算法思想
int i,j,min = INF;
s[startVex] = 1; //把startvex 選到s集合中去 -->這里為下面選擇最小值服務(wù)了 放在這里代碼思路清晰點(diǎn)
for( i = 0; i < VexNum; i++)
{
dist[i] = graph[startVex][i] ; //這里就是開(kāi)始貪心了 認(rèn)為 startVex ---> 各個(gè)定點(diǎn)距離現(xiàn)在就是最短了。
if(dist[i] < INF)
{
path[i] = startVex; //保存到i 最短路徑的前一個(gè)定點(diǎn)
}
else
{
path[i] = -1;
}
}
for(j = 0; j < VexNum; j++)
{
int min = INF;
int uVex = -1; //保存從沒(méi)有選過(guò)的點(diǎn)中距離最短的點(diǎn)
for( i = 0; i < VexNum; i++)
{
if(s[i] == 0) //過(guò)濾條件--->把選擇的點(diǎn)過(guò)濾掉
{
if( min > dist[i])
{
min = dist[i];
uVex = i;
}
}
}
//這樣就得到一個(gè)頂點(diǎn)了
if(uVex != -1)//為什么要判斷 因?yàn)?你可能沒(méi)有最小的選擇 但還在循環(huán)中的處理
{
s[uVex] = 1; //加入s集合 不加就會(huì)出現(xiàn)重復(fù)選擇一個(gè)點(diǎn) --->顯然這樣結(jié)果肯定是不對(duì)的
for(i = 0; i < VexNum; i++) //這里就是在修改dist 最短距離的值了 有可能幾個(gè)點(diǎn) 比你直接2個(gè)點(diǎn)要短
{//我們只要dist[i]+dist[j] < dist[j] 距離就可以了
if(s[i] == 0)///dist[i] 是dist 最短的 這里就體現(xiàn)了貪心法了。
{
if(dist[i] > dist[uVex] + graph[uVex][i])
{
path[i] = uVex; //保存到達(dá)i 點(diǎn) 最短距離的前一個(gè)點(diǎn)
dist[i] = dist[uVex] + graph[uVex][i];
}
}
}
}
}
cout<<"打印Dijkstra"<<endl;
/////////////////////////
int stack[MAXVEX] = {0};
int top = -1;
//一個(gè)簡(jiǎn)單棧
/////////////////////////
for(i = 0; i < VexNum; i++)
{
int pre = path[i]; //獲得到達(dá)i點(diǎn)最短路徑的前一個(gè)定點(diǎn)
if(pre != -1)
{
cout<<"dist: "<<dist[i]<<endl;
while(pre != startVex) //
{
stack[++top] = pre; //進(jìn)棧
pre = path[pre];
}
cout<<startVex<<"---->"<<i<<"路徑: ";
cout<<startVex<<" ";
while(top!=-1)
{
cout<<stack[top--]<<" ";
}
cout<<i<<endl;
}
else
{
cout<<startVex<<"--->"<<i<<"沒(méi)有路徑"<<endl;
}
}
}
int main()
{
int cost[6][MAXVEX] ={
{0,50,10,INF,INF,INF},
{INF,0,15,50,10,INF},
{20,INF,0,15,INF,INF},
{INF,20,INF,0,35,INF},
{INF,INF,INF,30,0,INF},
{INF,INF,INF,3,INF,0}};
Dijkstra(cost,1,6);
return 1;
}
如上圖：
假設(shè)1為起始點(diǎn)
我們會(huì)這樣想比喻1 ->0 ： 我們會(huì)比較 1->0 這2點(diǎn)直接相同不如果不相同我們肯定找別的通往0（也肯定要以1為起始點(diǎn)的撒）點(diǎn) ---》所以1->2->0 這樣就得到了。
其實(shí)這就是最短路徑的思路了 反正我學(xué)習(xí)的2個(gè)算法 Dijkstra 和Floyed 算法都是差不多這個(gè)思路。
我們貪心法恰好就是這個(gè)思路 我們找到起始點(diǎn) 這里是1 到各個(gè)點(diǎn)這里是0 , 2,3 路徑距離 然后修改到各個(gè)點(diǎn)的值 （dist[i]--我們認(rèn)為dist 放都是最短距離）。。這樣就會(huì)得到我們想要結(jié)果了
如我們這個(gè)例子：1—》0 : 我們會(huì)開(kāi)始的時(shí)候初始化 1->0 直接是為INF 無(wú)窮大 不通撒
1--3 是不是1 到各個(gè)點(diǎn)最短的不 不是 我們?cè)僬抑雷疃?/span> 的 這里是1 到2是最短的
這里我們就修改1->0值是dist[0] =60+102;1->3 值dist[3] =60+300;形成新dist。。
然后以繼續(xù)上面重復(fù)。。。。。。。。。
所以1 –》2-》0
這里我畫(huà)圖只畫(huà)了這幾個(gè) 所以 不能很好說(shuō)明
————————————————————————————————
弗洛伊德 思路起始也是差不多 只是邊邊 上面是點(diǎn)到點(diǎn)
//遞歸打印
void printPath(int start,int end,int path[][MAXVEX])
{
if(end != -1)
{
end = path[start][end];
printPath(start,end,path);
if(end!=-1)
cout<<end<<" ";
}
}
void Floyed(int cost[][MAXVEX],int n)
{
int A[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];
int i,j,k,pre;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
{
A[i][j] = cost[i][j];
path[i][j] = -1;
}
for( k = 0; k < n; k++)
{
for( i = 0; i < n; i++)
for( j = 0; j < n; j++)
if(A[i][j] > (A[i][k] + A[k][j]))
{
A[i][j] = A[i][k] + A[k][j];
path[i][j] = k;
}
}
printf("\n Floyed算法求解:\n");
for( i = 0; i < n; i++)
for(j = 0; j < n; j++)
if(i!=j)
{
printf(" %d->%d:",i,j);
if( A[i][j] == INF)
{
if(i!=j)
printf("不存在路徑\n");
}
else
{
printf("路徑長(zhǎng)度為:%3d",A[i][j]);
printf("路徑為%d ",i);
pre = path[i][j];
//////////////////
int stack[MAXVEX] = {0};
int top = -1;
//這里簡(jiǎn)單的棧 書(shū)上代碼是錯(cuò)誤的 打印是不對(duì)的 那本書(shū)的作者肯定是搞混了
////////////////
/*while(pre != -1)
{
//printf("%d ",pre);
stack[++top] = pre;
pre = path[i][pre];
}
while(top!=-1)
{
printf("%d ",stack[top--]);
}*/
printPath(i,j,path); //這里用的遞歸打印路徑
printf(" %d\n",j);
}
}
}
int main()
{
int cost[6][MAXVEX] ={
{0,50,10,INF,INF,INF},
{INF,0,15,50,10,INF},
{20,INF,0,15,INF,INF},
{INF,20,INF,0,35,INF},
{INF,INF,INF,30,0,INF},
{INF,INF,INF,3,INF,0}};
//Dijkstra(cost,6,1);
Floyed(cost,6);
return 1;
}