I. Уточнение:
mosт.е. Q согласен с Bely, что надо переводить неориентированный граф в ориентированный?

Слово "Нада" тут не правильное.
Например, получения всех узлов, имеющих дуги с узлом A можно сделать двумя способами:
1) Для неориентированного графа:
SELECT t_id2
FROM t_Rebra
WHERE t_id1 = A
UNION ALL
SELECT t_id1
FROM t_Rebra
WHERE t_id2 = A

2) Для ориентированного графа (записей в два раза больше, чем в неориентированном варианте):
SELECT t_id2
FROM t_Rebra
WHERE t_id1 = A

Поэтому совет: В случае с ориентированным графом - быстрее и проще запросы, но сложнее модификация данных, в случае неориентированного графа - сложнее и медленнее запросы, но проще модификация данных.
(Вообще - традиционная проблема: хочешь быстрее - плати ресурсами, хочешь меньше по объему - плати производительностью или по другому: считать результат можно каждый раз, а можно заранее посчитать и потом только пользоваться сохраненными результатами всей задачи или ее части).
Сами выбирайте что "лучше" для Вас!

II. Еще вариант (возможно это то, что предлагал Q, но я его не понял)
Хранить все возможные пути между всеми вершинами!
Этот вариант самый быстрый (с точки зрения решения запрашиваемых задач) и требующий больше всего ресурсов. А также имеющий сложности с вводом исходных данных (но это решаемо).

Конкретно:
Т.е. кроме предложенных таблиц (вариант неориентированного графа) дополняем еще пару:
puti (put_id, t_id1, t_id2, rastojanie) - каждая запись о возможном пути
shagi_puti(shag_puti_id, put_id, t_id1, t_id2, N, rastojanie) - запись о дуге, с ее узлами, номером шага в пути и растоянием, причем идем именно от t_id1 к t_id2.
Данную таблицу нужно автоматически перегенерировать при любом изменении t_Rebra.
Т.е. тратим много места на организацию новых таблиц (в них будет много записей - рост близкий к экспоненте от количества ребер и узлов), тратим время один (каждый) раз при внесении изменений в исходные таблицы для перегенерации ноых таблиц, но! заявленные задачи
mosВторое задание:
- найти самый короткий путь между двумя вершинами
- найти самый короткий путь от заданой вершины до определенного типа вершин
Выполняться будут очень быстро (индексы соответствующие не забываем сделать)!