#include <iostream>
#include <stdio.h>
using namespace std;
#define MAXVEX 100
#define INF 6000
//定義比較的數字 表示無窮大 只要比你圖中的權值運算涉及的值要大就可以了
/************************************************************************/
/* Dijkstra 算法思想
/* 1: 基本思想就是貪心法（核心思想） --->在寫代碼時候再說
/* 2: 這里就是找出源點到各個點最短距離 然后用這個最短距離+源點到另外一個點距離 如果< 就修改值這樣不斷修改就得出了
/************************************************************************/
void Dijkstra(int graph[][MAXVEX],int startVex,int VexNum)
{
int path[MAXVEX] = {-1}; //保存最終點最短路徑的前一個點
int dist[MAXVEX] = {0};
int s[MAXVEX] = {0}; //標志是否在s的集合中--> 這里要涉及到Dijkstra 算法思想
int i,j,min = INF;
s[startVex] = 1; //把startvex 選到s集合中去 -->這里為下面選擇最小值服務了 放在這里代碼思路清晰點
for( i = 0; i < VexNum; i++)
{
dist[i] = graph[startVex][i] ; //這里就是開始貪心了 認為 startVex ---> 各個定點距離現在就是最短了。
if(dist[i] < INF)
{
path[i] = startVex; //保存到i 最短路徑的前一個定點
}
else
{
path[i] = -1;
}
}
for(j = 0; j < VexNum; j++)
{
int min = INF;
int uVex = -1; //保存從沒有選過的點中距離最短的點
for( i = 0; i < VexNum; i++)
{
if(s[i] == 0) //過濾條件--->把選擇的點過濾掉
{
if( min > dist[i])
{
min = dist[i];
uVex = i;
}
}
}
//這樣就得到一個頂點了
if(uVex != -1)//為什么要判斷 因為 你可能沒有最小的選擇 但還在循環中的處理
{
s[uVex] = 1; //加入s集合 不加就會出現重復選擇一個點 --->顯然這樣結果肯定是不對的
for(i = 0; i < VexNum; i++) //這里就是在修改dist 最短距離的值了 有可能幾個點 比你直接2個點要短
{//我們只要dist[i]+dist[j] < dist[j] 距離就可以了
if(s[i] == 0)///dist[i] 是dist 最短的 這里就體現了貪心法了。
{
if(dist[i] > dist[uVex] + graph[uVex][i])
{
path[i] = uVex; //保存到達i 點 最短距離的前一個點
dist[i] = dist[uVex] + graph[uVex][i];
}
}
}
}
}
cout<<"打印Dijkstra"<<endl;
/////////////////////////
int stack[MAXVEX] = {0};
int top = -1;
//一個簡單棧
/////////////////////////
for(i = 0; i < VexNum; i++)
{
int pre = path[i]; //獲得到達i點最短路徑的前一個定點
if(pre != -1)
{
cout<<"dist: "<<dist[i]<<endl;
while(pre != startVex) //
{
stack[++top] = pre; //進棧
pre = path[pre];
}
cout<<startVex<<"---->"<<i<<"路徑: ";
cout<<startVex<<" ";
while(top!=-1)
{
cout<<stack[top--]<<" ";
}
cout<<i<<endl;
}
else
{
cout<<startVex<<"--->"<<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;
}
如上圖：
假設1為起始點
我們會這樣想比喻1 ->0 ： 我們會比較 1->0 這2點直接相同不如果不相同我們肯定找別的通往0（也肯定要以1為起始點的撒）點 ---》所以1->2->0 這樣就得到了。
其實這就是最短路徑的思路了 反正我學習的2個算法 Dijkstra 和Floyed 算法都是差不多這個思路。
我們貪心法恰好就是這個思路 我們找到起始點 這里是1 到各個點這里是0 , 2,3 路徑距離 然后修改到各個點的值 （dist[i]--我們認為dist 放都是最短距離）。。這樣就會得到我們想要結果了
如我們這個例子：1—》0 : 我們會開始的時候初始化 1->0 直接是為INF 無窮大 不通撒
1--3 是不是1 到各個點最短的不 不是 我們再找知道最短 的 這里是1 到2是最短的
這里我們就修改1->0值是dist[0] =60+102;1->3 值dist[3] =60+300;形成新dist。。
然后以繼續上面重復。。。。。。。。。
所以1 –》2-》0
這里我畫圖只畫了這幾個 所以 不能很好說明
————————————————————————————————
弗洛伊德 思路起始也是差不多 只是邊邊 上面是點到點
//遞歸打印
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("路徑長度為:%3d",A[i][j]);
printf("路徑為%d ",i);
pre = path[i][j];
//////////////////
int stack[MAXVEX] = {0};
int top = -1;
//這里簡單的棧 書上代碼是錯誤的 打印是不對的 那本書的作者肯定是搞混了
////////////////
/*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;
}
posted on 2012-05-23 22:38
小魚兒 閱讀(273)
評論(0) 編輯 收藏 引用