📄 一个顶点到其他各顶点的最短路径.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0068)http://www.cs.ecnu.edu.cn/assist/js04/ZJS045/ZJS04505/zjs045050a.htm -->
<HTML><HEAD><TITLE>无标题文档</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<SCRIPT language=JavaScript>
/*
Made By Eddie Traversa.
*/
float_init = 1;
function DHTML_Init(Object) {
if (navigator.userAgent.match(/Mozilla\/5\../) && float_init) {
SetObjectOffsetTop(Object, undefined);
} }
function All (ID) {
if (document.all) { return document.all[ID]; }
else if (document.documentElement){
return document.getElementById (ID); }
else if (document.layers) { return document.layers[ID]; }}
function GetWindowOffsetTop() {
if (window.innerHeight) { return window.pageYOffset; }
else if (document.body) { return document.body.scrollTop; }}
function GetWindowHeight() {
if (window.innerHeight) { return window.innerHeight; }
else if (document.body) { return document.body.clientHeight; }}
function GetObjectHeight(Object) {
DHTML_Init(Object);
if (document.all || document.documentElement) {
Clip = Object.style.clip;
if (! Clip) { return Object.offsetHeight; }
else { return GetClipElement (Clip, 'Bottom'); }}
else if (document.layers) { return Object.clip.height; }}
function GetClipElement (Clip, Element) {
Clip = Clip.substr(Clip.indexOf('(') + 1);
Clip = Clip.substr(0, Clip.length - 1);
Clippers = Clip.split (" ");
for (i = 0; i < Clippers.length; i++) {
if (Clippers[i] != 'auto')
{ Clippers[i] = Clippers[i].replace (/D/g, ""); }}
ClipTop = Number(Clippers[0]);
ClipRight = Number(Clippers[1]);
ClipBottom = Number(Clippers[2]);
ClipLeft = Number(Clippers[3]);
if (Element == 'Top') { return ClipTop; }
else if (Element == 'Right') { return ClipRight; }
else if (Element == 'Bottom') { return ClipBottom; }
else if (Element == 'Left') { return ClipLeft; }
else { return undefined; }}
function GetObjectOffsetTop(Object) {
DHTML_Init(Object);
if (Object.offsetTop) { return Object.offsetTop; }
else if (document.layers) { return Object.top; }}
function SetObjectOffsetTop(Object, Offset) {
if (Object.style) { Object.style.top = Offset; }
else if (Object.top) { Object.top = Offset; }}
CenterMenu = 1;
MenuBorder = 100;
TimeCheck = 250;
TimeUpdate = 15;
DivUpdate = 15;
Minimum = 50;
AddHeight = -4;
function ScrollMenu() {
Menu = All('Layer2');
WinTop = GetWindowOffsetTop();
WinHeight = GetWindowHeight() + AddHeight;
MenuTop = GetObjectOffsetTop(Menu);
MenuHeight = GetObjectHeight (Menu);
MenuNew = (CenterMenu) ? Math.round (WinTop + (WinHeight - MenuHeight) / 3) : WinTop + MenuBorder;
if (MenuNew < Minimum)
{ MenuNew = Minimum; }
if (MenuTop != MenuNew) {
if ( (MenuTop + MenuHeight) < WinTop || MenuTop > (WinTop + WinHeight) ) {
SetObjectOffsetTop (Menu, (MenuTop < MenuNew) ? (WinTop - MenuHeight) : (WinTop + WinHeight));
} else {
Add = (MenuTop < MenuNew) ? 1 : -1;
SetObjectOffsetTop (Menu, MenuTop + Math.round((MenuNew - MenuTop) / DivUpdate) + Add);
}
}
window.setTimeout('ScrollMenu()', (GetObjectOffsetTop(Menu) == MenuNew) ? TimeCheck : TimeUpdate);
}
</SCRIPT>
<LINK href="Title2.css" type=text/css rel=stylesheet><LINK href="Title1.css"
type=text/css rel=stylesheet>
<META content="MSHTML 5.50.4134.600" name=GENERATOR></HEAD>
<BODY text=#ffffff vLink=#ffffff aLink=#ffffff link=#ffffff bgColor=#3098c8
onload=ScrollMenu()>
<P> </P>
<DIV id=Layer1
style="Z-INDEX: 1; LEFT: 290px; VISIBILITY: hidden; WIDTH: 160px; POSITION: absolute; TOP: 9px; HEIGHT: 148px">
<TABLE class=text width=216 border=1>
<TBODY>
<TR>
<TD class=text bgColor=#306498>
<DIV align=center><FONT color=#00ff33 size=2>５.1 <FONT color=#ffffff><A
target=_top
href="http://www.cs.ecnu.edu.cn/assist/js04/ZJS045/zjs04501/zjs044010.htm">图的基本概念</A></FONT></FONT></DIV></TD></TR>
<TR>
<TD class=text bgColor=#306498>
<DIV align=center><FONT color=#33ff00 size=2>5.2 <FONT color=#ffffff><A
target=_top
href="http://www.cs.ecnu.edu.cn/assist/js04/ZJS045/zjs04502/zjs045020.htm">图的存储结构</A></FONT></FONT></DIV></TD></TR>
<TR>
<TD class=text bgColor=#306498>
<DIV align=center><FONT color=#33ff00 size=2>5.3 <FONT color=#00cc00><A
target=_top
href="http://www.cs.ecnu.edu.cn/assist/js04/ZJS045/zjs04503/zjs0450300.htm">图的遍历</A></FONT></FONT></DIV></TD></TR>
<TR>
<TD class=text bgColor=#306498>
<DIV align=center><FONT color=#33ff00 size=2>5.4 <FONT color=#ffffff><A
target=_top
href="http://www.cs.ecnu.edu.cn/assist/js04/ZJS045/zjs04504/zjs045040.htm">生成树和最小生成树</A></FONT></FONT></DIV></TD></TR>
<TR>
<TD class=text bgColor=#306498>
<DIV align=center><FONT color=#33ff00 size=2>5.5 <FONT color=#ffffff><A
target=_top
href="http://www.cs.ecnu.edu.cn/assist/js04/ZJS045/ZJS04505/zjs0450500.htm">最短路径问题</A></FONT></FONT></DIV></TD></TR>
<TR>
<TD class=text bgColor=#306498>
<DIV align=center><FONT color=#00ff00 size=2>5.6</FONT><FONT color=#ffffff
size=2> <A target=_top
href="http://www.cs.ecnu.edu.cn/assist/js04/ZJS045/zjs04506/zjs0450600.htm">拓扑排序</A></FONT></DIV></TD></TR></TBODY></TABLE></DIV>
<DIV id=Layer2
style="Z-INDEX: 1; LEFT: 15px; WIDTH: 69px; POSITION: absolute; TOP: 107px; HEIGHT: 128px">
<P><A
href="http://www.cs.ecnu.edu.cn/assist/js04/ZJS045/ZJS04505/zjs045050a.htm#top"><IMG
height=32 alt=回到首页 src="一个顶点到其他各顶点的最短路径.files/zp0450306.gif" width=32
border=0></A></P>
<P><A target=_top
href="http://www.cs.ecnu.edu.cn/assist/js04/zjs040/zjs00/zjs01000.htm"><IMG
height=32 src="一个顶点到其他各顶点的最短路径.files/zp0450307.gif" width=32 border=0></A></P>
<P> </P></DIV>
<P align=center><A name=top></A><IMG height=23
src="一个顶点到其他各顶点的最短路径.files/zp0450500.jpg" width=178></P>
<TABLE width=676 align=center bgColor=#306498 border=1>
<TBODY>
<TR>
<TD width=666>
<TABLE height=119 width=669 border=1>
<TBODY>
<TR>
<TD width=659 height=113>
<P><FONT color=#ffffff
size=2>在一个图中，两个结点之间可能有多条路径，且每条路径上所经过的边数可能是不同的，如果是网络，每条路径的各边权数之和也可能是不同的。我们通常把<FONT
color=#00cc00>从一个指定的顶点到达另一指定顶点的各边权数之和为最小的路径称为最短路径</FONT>，这
类问题亦称为<FONT
color=#00cc00>最短路径问题</FONT>。例如，用顶点表示城市，边表示路径，而边上的权表示里程数，于是顶点、边及里程数构成了一个有关城市的网络，我们从某一城市到达另外城市的最省路径便是一个典型的最短路径问题。
</FONT><BR></P></TD></TR></TBODY></TABLE></TD></TR>
<TR>
<TD>
<TABLE height=94 width=670 border=1>
<TBODY>
<TR>
<TD width=660 height=88>
<P><FONT color=#00ff00 size=2>[提高<FONT color=#00cc00>]</FONT><FONT
color=#ffffff>(增)</FONT></FONT></P>
<P><FONT color=#ffffff size=2>本节考虑的是<FONT
color=#00cc00>带权有向图</FONT>,除非特别声明,否则有向边上的权总是正的.我们称路径的开始顶点为<FONT
color=#00cc00>源点</FONT>,称路径的最后顶点为<FONT color=#00cc00>终点</FONT>.<FONT
color=#00cc00>路径的长度</FONT>是该路径上各边的权之和.<BR></FONT></P></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE>
<P> </P>
<P>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -