交通網絡中的一些問題及算法

摘要本文針對一類交通網絡，利用最短路算法，建立了交通網絡中等待次數最少的通路算法。

關鍵詞交通網絡臨時標號永久標號

中圖分類號:O13文獻標識碼:A

1 引言

在各大中城市，隨著機動車輛的不斷增加，交通擁擠現象已成為廣大職工上下班深為關注的一個熱點。而“堵”又是最感頭痛的問題之一。

本文對一類交通網絡，按照交通規則，提出了一個計算等待綠燈次數最少的通路算法，從一個方面解決了這個問題。

2 模型及算法

設為一個無向圖，這里為的頂點集，為的邊集，對每一頂點，我們賦一個權(只取0，1兩個值)，其值依交通規則確定如下:

現圖示如下:

其中(c)可視為(b)的特例。

根據交通規則，上面三圖中除車輛遇紅燈往右拐不需等待外，其余各方向皆要等待一次。

另外，對一個交叉路口處，即一個頂點，若有五叉或五叉以上路口，可在該交叉路口處設立交橋，所以不必考慮。

我們的問題是，在賦權的無向圖上，尋找一條從(出發點)到(終點)的等待次數最少的通路，我們不妨從始點出發，逐步往前行，從始點尋找到下一個點等待次數最少的通路，逐步往下延伸，最終到達終點。當然，對于一個點，若有任意條以為終點的通路時，應取到等待次數最少的一條通路。如圖1，此時，應取等待次數為1的兩條通路中的任一條。

這里，我們規定，，經到方向的等待次數標在的右邊，如圖2，2表示從始點到共等待2次。

具體算法(不考慮時間):

我們以表示的臨時標號，以表示的永久標號。……