資源簡介
目前網絡上電子地圖的使用很普遍。利用電子地圖可以很方便地確定從一個地點到另一個地點的路徑。特別地，可確定在城市中的公交換乘路線。
電子地圖可以看成是一個圖，而公交線路圖可看成是帶權有向圖G =(V,E)，其中每條邊的權是非負實數。
最短路徑問題：計算從給定的起點s到另一個頂點t的最短路徑的長度。
你的任務：對給定的一個（無向）圖G，及G中的兩點s、t，計算從起點s到頂點t的最短距離。
代碼片段和文件信息
/*#include??
#include??
using?namespace?std;?
void?Dijkstra（int?nint?vint?dist[]int?prev[]int?**c）?
{?
int?maxint?=?65535;?
//int?maxint?=?-1;?
bool?*s?=?new?bool[n];?
for?（int?i?=?1;?i?<=?n;?i++）?
{?
dist[i]?=?c[v][i];?
s[i]?=?false;?
if?（dist[i]?==?maxint）?
prev[i]?=?0;?
else?
prev[i]?=?v;?
}?
dist[v]?=?0;?
s[v]?=?true;?
for?（int?i?=?1;?i? {?
int?temp?=?maxint;?
int?u?=?v;?
for?（int?j?=?1;?j?<=?n;?j++）?
{?
if?（（!s[j]）?&&?（dist[j]? //if?（（!s[j]）?&&?（dist[j]?>=?temp））?
{???
u?=?j;?
temp?=?dist[j];?
}??
}?
s[u]?=?true;?
for?（int?j?=?1;?j?<=?n;?j++）?
{???
if?（（!s[j]）?&&?（c[u][j]? //if?（（!s[j]）?&&?（c[u][j]?>=?maxint））?
{???
?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件????????3654??2015-07-03?18:09??4-c\4-c.cpp
?????文件????????1433??2015-07-03?18:09??4-c\4-c.msp
?????目錄???????????0??2015-07-04?14:11??4-c\Debug\
?????文件??????547378??2015-07-03?18:09??4-c\Debug\4-c.exe
?????文件??????126698??2015-07-03?18:09??4-c\Debug\4-c.o
?????目錄???????????0??2015-07-04?14:11??4-c\
- 上一篇：數據庫及ADO.NET（ppt）
- 下一篇：dmieditwin32
評論
共有 條評論